leetcode18四数之和（c++和python）

目录

题目描述&＃xff1a;

解题思路&＃xff1a; 

C&＃43;&＃43;代码&＃xff1a;

python代码&＃xff1a;

题目描述&＃xff1a;

给定一个包含 n 个整数的数组 nums 和一个目标值 target&＃xff0c;判断 nums 中是否存在四个元素 a&＃xff0c;b&＃xff0c;c 和 d &＃xff0c;使得 a &＃43; b &＃43; c &＃43; d 的值与 target 相等&＃xff1f;找出所有满足条件且不重复的四元组。

注意&＃xff1a;

答案中不可以包含重复的四元组。

示例&＃xff1a;

给定数组 nums &＃61; [1, 0, -1, 0, -2, 2]&＃xff0c;和 target &＃61; 0。满足要求的四元组集合为&＃xff1a;
[[-1, 0, 0, 1],[-2, -1, 1, 2],[-2, 0, 0, 2]
]

解题思路&＃xff1a; 

先排序&＃xff0c;在定四个索引: a, b, c, d;  其中a&＃xff0c; b依次从头到尾开始遍历&＃xff0c;c定在b&＃43;1&＃xff0c;d定在nums.size()-1, 然后c, d慢慢靠拢。如果nums[a] &＃43; nums[b] &＃43; nums[c] &＃43; nums[d] > target&＃xff0c;在前面基数a,b固定的情况下&＃xff0c;则只能移动d--&＃xff0c;才能使和变小&＃xff0c;才有可能找到相等的索引&＃xff0c;反之如果

C&＃43;&＃43;代码&＃xff1a;

执行用时&＃xff1a;112 ms, 在所有 C&＃43;&＃43; 提交中击败了20.99%的用户

内存消耗&＃xff1a;12.6 MB, 在所有 C&＃43;&＃43; 提交中击败了87.95%的用户

class Solution {
public:vector> fourSum(vector& nums, int target) {int len_nums &＃61; nums.size();if (len_nums <4) return {};sort(nums.begin(), nums.end());vector> ans;for (int i &＃61; 0; i 0 && nums[i] &＃61;&＃61; nums[i-1]) continue; // 后面的数字和前面的重复了&＃xff0c;则直接跳过for (int j &＃61; i&＃43;1; j i&＃43;1 && nums[j] &＃61;&＃61; nums[j-1]) continue; // 后面的数字和前面的重复了&＃xff0c;则直接跳过int L &＃61; j&＃43;1; // L指向四个数中第三个元素int R &＃61; len_nums-1;while (L targetif (nums[i]&＃43;nums[j]-target > -(nums[L]&＃43;nums[R])) R--; // 大了&＃xff0c;则移动右边else if (nums[i]&＃43;nums[j]-target <-(nums[L]&＃43;nums[R])) L&＃43;&＃43;; // 小了&＃xff0c;则移动左边else{ans.push_back({nums[i], nums[j], nums[L], nums[R]}); // 找到了合适的&＃xff0c;如果后面元素重复则跳过while (L };

python代码&＃xff1a;

执行用时&＃xff1a;476 ms, 在所有 Python 提交中击败了64.67%的用户

内存消耗&＃xff1a;13 MB, 在所有 Python 提交中击败了78.96%的用户

class Solution(object):def fourSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[List[int]]"""len_nums &＃61; len(nums)if len_nums <4: return []nums.sort() # 有序数组ans &＃61; []for i in range(len_nums - 3):if i > 0 and nums[i] &＃61;&＃61; nums[i-1]: continue # 重复了&＃xff0c;则跳过for j in range(i &＃43; 1, len_nums - 2):if j > i&＃43;1 and nums[j] &＃61;&＃61; nums[j-1]: continueL &＃61; j &＃43; 1R &＃61; len_nums - 1while L target:R &＃61; R - 1elif sum_val