c++-c++编程基础之leetcode题解第18题四数之和.zip资源-CSDN下载

共1个文件

md：1个

需积分: 50 152 浏览量 2024-03-18 05:23:06 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升算法与数据结构技能。本资源包聚焦于解决LeetCode中的第18题——"四数之和"（4Sum）。这是一个典型的数组操作问题，对于学习C++基础和进阶算法的程序员来说，具有很高的实践价值。题目描述：给定一个整数数组`nums`和一个目标值`target`，请你在该数组中找出和为目标值的那四个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。例如，给定数组`nums = [1, 0, -1, 0, -2, 2]`和`target = 0`，一个可能的答案是`[0, 1, 2, 3]`，因为`nums[0] + nums[1] + nums[2] + nums[3] = 0`，且`0 <= index1 < index2 < index3 < index4`。解决这个问题的关键在于理解如何有效地搜索数组中的四个数，使得它们的和等于目标值。以下是一种可能的解决方案： 1. 我们需要对数组`nums`进行排序，这可以通过C++的`std::sort`函数实现。排序可以简化后续的查找过程，因为我们可以利用有序数组的性质来降低时间复杂度。 ```cpp std::sort(nums.begin(), nums.end()); ``` 2. 接着，我们使用三个嵌套循环来遍历数组。外层循环`i`从0到`n-3`，其中`n`是数组长度，确保我们有足够多的元素组成四数之和。 3. 内部的两个循环`j`和`k`分别从`i+1`到`n-2`和`j+1`到`n-1`。为什么要从`i+1`开始呢？因为我们不希望重复使用同一个元素，所以`j`不能等于`i`。同理，`k`不能等于`j`以避免重复组合。 4. 在每次迭代中，我们计算当前三数之和`sum = nums[i] + nums[j] + nums[k]`，然后用目标值`target`减去`sum`，得到`temp`。接着，我们用双指针法在一个已排序的数组`nums`中查找`temp`的值。左指针`l`从`k+1`开始，右指针`r`从`n-1`开始。如果`nums[l] + nums[r] > temp`，我们将`r--`；反之，如果`nums[l] + nums[r] < temp`，我们将`l++`。当找到合适的`nums[l] + nums[r] = temp`时，我们找到了一个四数之和为`target`的解。 5. 找到一个解后，我们需要记录下四个数的索引，可以使用`std::vector<int>`来存储结果，并在每次找到解时调用`result.push_back()`。 6. 返回结果数组`result`。这个解决方案的时间复杂度是`O(n^3)`，因为有三层循环。虽然不是最优解，但对于理解和实践C++编程以及基本的算法思想来说，这个方法已经足够了。在实际应用中，可以考虑使用哈希表或更高级的数据结构来优化成`O(n^2)`的时间复杂度。通过解决这道LeetCode题目，开发者可以熟悉C++的基础语法、排序、数组操作以及算法设计。这对于提高编程能力和解决实际问题的能力是非常有益的。同时，这也能帮助程序员为面试做准备，因为在许多技术面试中，类似的问题经常被用来测试候选人的编程和算法能力。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第18题四数之和.zip （1个子文件）

c++_c++编程基础之leetcode题解第18题四数之和

README.md 3KB

# [18. 4Sum (Medium)](https://leetcode.com/problems/4sum/) Given an array <code>nums</code> of <code>n</code> integers, return an array of all the unique quadruplets <code>[nums[a], nums[b], nums[c], nums[d]]</code> such that: <ul> <li><code>0 <= a, b, c, d < n</code></li> <li><code>a</code>, <code>b</code>, <code>c</code>, and <code>d</code> are distinct.</li> <li><code>nums[a] + nums[b] + nums[c] + nums[d] == target</code></li> </ul> You may return the answer in any order.   Example 1: <pre>Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] </pre> Example 2: <pre>Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]] </pre>   Constraints: <ul> <li><code>1 <= nums.length <= 200</code></li> <li><code>-109 <= nums[i] <= 109</code></li> <li><code>-109 <= target <= 109</code></li> </ul> **Companies**: [Amazon](https://leetcode.com/company/amazon), [Bloomberg](https://leetcode.com/company/bloomberg), [Adobe](https://leetcode.com/company/adobe), [Yahoo](https://leetcode.com/company/yahoo), [Snapchat](https://leetcode.com/company/snapchat) **Related Topics**: [Array](https://leetcode.com/tag/array/), [Two Pointers](https://leetcode.com/tag/two-pointers/), [Sorting](https://leetcode.com/tag/sorting/) **Similar Questions**: * [Two Sum (Easy)](https://leetcode.com/problems/two-sum/) * [3Sum (Medium)](https://leetcode.com/problems/3sum/) * [4Sum II (Medium)](https://leetcode.com/problems/4sum-ii/) ## Solution 1. Two Pointers The brute force solution is to enumerating all quadruplets. It will take `O(N^4)` time. Since `N^4 = 1.6e9`, we will get TLE. We can enumerate the first two elements and use two pointers to get the last two elements, reducing the time complexity to `O(N^3)`. (`N^3 = 8e6`) ```cpp // OJ: https://leetcode.com/problems/4sum/ // Author: github.com/lzl124631x // Time: O(N^3) // Space: O(1) class Solution { public: vector<vector<int>> fourSum(vector<int>& A, int target) { int N = A.size(); sort(begin(A), end(A)); vector<vector<int>> ans; for (int i = 0; i < N; ++i) { if (i > 0 && A[i] == A[i - 1]) continue; for (int j = i + 1; j < N; ++j) { if (j > i + 1 && A[j] == A[j - 1]) continue; int t = target - A[i] - A[j]; for (int p = j + 1, q = N - 1; p < q; ) { if (A[p] + A[q] == t) { ans.push_back({ A[i], A[j], A[p++], A[q--] }); while (p < q && A[p] == A[p - 1]) ++p; while (p < q && A[q] == A[q + 1]) --q; } else if (A[p] + A[q] < t) ++p; else --q; } } } return ans; } }; ```

评论收藏

内容反馈