数组3sum-leetcode练习题

约定不等于承诺〃 2023-07-22 07:00 46阅读 0赞

![gif.latex][]

import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 
 
 /**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
 * 请你找出所有满足条件且不重复的三元组。
 * 
 * 注意：答案中不可以包含重复的三元组。
 * 
 * 
 * 
 * 示例：
 * 
 * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * 
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
 class Solution {
 
 public List<List<Integer>> threeSum(int[] nums) {
 if (nums == null || nums.length < 3) {
 return new ArrayList<>();
 }
 Arrays.sort(nums);
 List<List<Integer>> res = new ArrayList<>();
 for (int i = 0; i < nums.length - 2; i++) {
 int first = nums[i];
 if (first > 0) {
 break;
 }
 // i-1前面的值已经算过了，相等的值的情况下就不要再次计算了
 if (i > 0 && nums[i] == nums[i - 1]) {
 continue;
 }
 addTwoSum(nums, res, i + 1, nums.length - 1, -first);
 }
 return res;
 }
 
 private void addTwoSum(int[] nums, List<List<Integer>> res, int left, int right, int first) {
 int start = left;
 int end = right;
 while (left < right) {
 // left-1左边的值已经计算过了，不需要重复计算
 while (left > start && left < right && nums[left] == nums[left - 1]) {
 left++;
 }
 // right+1右边的值已经计算过了，不需要重复计算
 while (right < end && left < right && nums[right] == nums[right + 1]) {
 right--;
 }
 if (left >= right) break;
 int second = nums[left];
 int third = nums[right];
 int twoNum = second + third;
 if (first == twoNum) {
 List<Integer> temp = new ArrayList<>(3);
 temp.add(first);
 temp.add(second);
 temp.add(third);
 res.add(temp);
 left++;
 right--;
 } else if (first < twoNum) {
 right--;
 } else {
 left++;
 }
 }
 }
 }
 
 public class MainClass {
 public static int[] stringToIntegerArray(String input) {
 input = input.trim();
 input = input.substring(1, input.length() - 1);
 if (input.length() == 0) {
 return new int[0];
 }
 
 String[] parts = input.split(",");
 int[] output = new int[parts.length];
 for (int index = 0; index < parts.length; index++) {
 String part = parts[index].trim();
 output[index] = Integer.parseInt(part);
 }
 return output;
 }
 
 public static String integerArrayListToString(List<Integer> nums, int length) {
 if (length == 0) {
 return "[]";
 }
 String result = "";
 for (int index = 0; index < length; index++) {
 Integer number = nums.get(index);
 result += Integer.toString(number) + ", ";
 }
 return "[" + result.substring(0, result.length() - 2) + "]";
 }
 
 public static String integerArrayListToString(List<Integer> nums) {
 return integerArrayListToString(nums, nums.size());
 }
 
 public static String int2dListToString(List<List<Integer>> nums) {
 StringBuilder sb = new StringBuilder("[");
 for (List<Integer> list : nums) {
 sb.append(integerArrayListToString(list));
 sb.append(",");
 }
 sb.setCharAt(sb.length() - 1, ']');
 return sb.toString();
 }
 
 public static void main(String[] args) throws IOException {
 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 String line;
 while ((line = in.readLine()) != null) {
 int[] nums = stringToIntegerArray(line);
 List<List<Integer>> ret = new Solution().threeSum(nums);
 String out = int2dListToString(ret);
 System.out.print(out);
 }
 }
 }

优化思路：  
①a+b+c=0转化为a+b=-c  
②排序+从中间往两头夹的方式+减少不必要的重复计算

遍历排序后的数组，如果当前元素已经大于0了，就直接break  
    排序后从两边往中间夹，直到相遇结束循环  
    如果之前相等的元素已经检查过了，就直接跳过该元素，防止重复计算和结果重复。

[gif.latex]: https://private.codecogs.com/gif.latex?