public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); int k = 0; // k 的循环 while(k < nums.length - 3){ long threeTarget = target - nums[k]; int i = k + 1; // i 在剩余区间上执行"三数之和" while(i < nums.length - 2) { long twoTarget = threeTarget - nums[i]; int left = i + 1; int right = nums.length - 1; // left 和 right 在剩余区间上执行"两数之和"(对撞双指针) while(left < right) { List<Integer> inList = new ArrayList<>(); if(nums[left] + nums[right] > twoTarget) { right--; }else if(nums[left] + nums[right] < twoTarget) { left++; }else { // left 和 right 的去重 while(left < right && nums[right] == nums[right - 1]) { right--; } while(left < right && nums[left] == nums[left + 1]){ left++; } inList.add(nums[k]); inList.add(nums[i]); inList.add(nums[left]); inList.add(nums[right]); list.add(inList); left++; right--; } } // i 的去重 i++; while(nums[i] == nums[i - 1] && i < nums.length - 2) { i++; } } // k 的去重 k++; while(nums[k] == nums[k - 1] && k < nums.length - 3) { k++; } } return list; }
四数之和
发布时间 2023-10-29 19:32:24作者: 樱圃