[数据结构与算法]代码随想录哈希表——四数之和

题目

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

注意：

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

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1,
0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路

• 三数之和的双指针是一层fior循环nums[i]为确定值
• 四数之和的双指针是两层fior循环nums[k] + nums[i]为确定值，然后继续双指针循环，找到nums[k]+nums[i]+nums[left]+nums[right] == target的情况

剪枝

1. 三数之和中剪枝的操作是

nums[i] > 0

即可，因为三数之和的target是0，是一个确定的值，而且数组排序过，所以第一个数大于0的话就可以剪掉了。

2. 而在本题四数之和中的target是任意值，可以是负数，所以剪枝操作为

nums[i] > target && (nums[i] >=0 || target >= 0)

否则的话，比如数组是[-4, -3, -2, -1]，target是-10，没有(nums[i] >=0 || target >= 0)条件只有nums[i] > target条件的话，因为-4>-10，所以会pass掉这个结果集

去重

代码注释中解释

java代码

class Solution{
	public List<List<Integer>> fourSum(int[] nums,int target){
		List<List<Integer>> result = new ArrayList<>();
		Arrays.sort(nums);
		for(int k = 0;k < nums.length;k++){//多了一层for循环，来确定nums[k]+ nums[i]的值
			if(nums[k] > 0 && nums[k] > target){
				return result;//剪枝,直接返回
			}
			if(k > 0 && nums[k] == nums[k-1]){//去重，直接终止进行下一个循环
				continue;
			}
			for(int i = k+1;i< nums.length; i++){
				if(i > k+1 && nums[i] == nums[i-1]){//因为i和k是相邻的，所以要i从k+2开始
					continue;
				}
				int left = i+1;
				int right =nums.length-1;
				while(right > left){
					long sum = (long)nums[k]+nums[i]+nums[left]+nums[right];
					if(sum > target){
						right--;
					}else if(sum < target){
						left++;
					}else{
						result.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));//数组要转化成集合
						while(right > left && nums[right] == nums[right-1]) right--;
						while(right > left && nums[left] == nums[left+1]) left++;
						left++;
						right--;
					}
				} 
			}
		}
		return result;
	}
}