题目链接
题目:
分析:
- 我们已经知道三数之和如何求取, 并去重了 三数之和
- 那么四数之和同理, 需要固定两个数a和b 然后用"双指针算法" , 只要两指针之和等于target-a-b即可
- 同样对于四个数都要进行去重
代码:
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);int a = 0;int n = nums.length;while (a < n-3) {int b = a + 1;while (b < n-2) {int left = b + 1;int right = n - 1;long t1 = (long)target - nums[a] - nums[b];while (left < right) {int sum = nums[left] + nums[right];if (sum > t1) {right--;} else if (sum < t1) {left++;} else {list.add(Arrays.asList(nums[a], nums[b], nums[left], nums[right]));left++;right--;while (nums[left] == nums[left - 1] && left < right) {left++;}while (nums[right] == nums[right + 1] && left < right) {right--;}}}b++;while (nums[b] == nums[b - 1] && b < n-2) {b++;}}a++;while (nums[a] == nums[a - 1] && a < n-3) {a++;}}return list;}
}