算法-哈希表篇08-四数之和

四数之和

力扣题目链接

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。

解题思路

这道题其实就是三数之和的进阶版，做完三数之和，这道题就会做了，就是在三数之和的前提上多加一层循环。 解题过程：

先对数组进行排序；进行双循环遍历两个元素，在遍历这两个元素的时候都需要判断两次；条件一为自己与上一个元素不相等，否则跳过这个元素；（防止元素重复）条件二为该元素小于target或者小于0，否则直接结束循环；（这个元素已经大于target且大于0了，所以不可能组成一个答案）然后和三数之和一样，定义做右指针在剩下范围的左右两侧，向中间收缩，直到左右指针相遇或者出现答案；收缩时需要注意，如果出现和上一个元素相等的情况需要继续收缩，防止答案重复；当出现所需要的答案时，保存在答案数组中即可。 题解 class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size(); i++){ if(nums[i] > target && nums[i] > 0){ break; } if(i > 0 && nums[i] == nums[i - 1]){ continue; } for(int j = i + 1; j < nums.size(); j++){ if(nums[i] + nums[j] > target && nums[i] + nums[j] > 0){ break; } if(j > i + 1 && nums[j] == nums[j - 1]){ continue; } int l = j + 1, r = nums.size() - 1; while(l < r){ if((long)nums[i] + nums[j] + nums[l] + nums[r] == target){ ans.push_back({nums[i], nums[j], nums[l], nums[r]}); while(l < r && nums[r] == nums[r - 1]){ r--; } while(l < r && nums[l] == nums[l + 1]){ l++; } r--; l++; } else if((long)nums[i] + nums[j] + nums[l] + nums[r] > target){ r--; } else if((long)nums[i] + nums[j] + nums[l] + nums[r] < target){ l++; } } } } return ans; } }; 总结

在被三数之和反复折磨之后，算是理解了枝剪去重的操作，这次写四数之和的整体思路是对的，但是还是出现了很多小问题。力扣不能debug振刀好难受啊。