java 如何优化ThreeSum(LeetCode)解决方案?

fcg9iug3  于 2023-04-10  发布在  Java
关注(0)|答案(1)|浏览(162)

原始问题陈述:
给定一个整数数组nums,返回所有三元组[nums[i],nums[j],nums[k]],使得i!= j,i!= k,j!= k,并且nums[i] + nums[j] + nums[k] == 0。
请注意,解决方案集不得包含重复的三元组。
我的解决方案:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); 
        List<List<Integer>> ans = new ArrayList<List<Integer>>(); 
        ArrayList<Integer> temp; 
        int left, right, sum;
        for(int i = 0; i < nums.length; i++){
            left = i+1; 
            right = nums.length - 1;
            while(left < right){
                sum = nums[i] + nums[left] + nums[right]; 
                if(sum == 0){
                    temp = new ArrayList<Integer>(); 
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    if(ans.contains(temp) == false){
                        ans.add(temp);
                        left++;
                        continue;
                    }
                    left++;
                    continue;
                }else if(sum<0){
                    left++; 
                    continue;
                }else{
                    right--; 
                    continue;
                }
            }
        }
        return ans; 
    }
}

我在LeetCode的测试用例311/312中得到了TLE,这是一个非常大的数组,值也很大。我一直在寻找一种方法来优化它,但似乎想不出答案。我真的很感激任何关于该怎么做的提示。谢谢。

cyej8jka

cyej8jka1#

有一个问题(bug),在找到具有相同值的其他List示例时,List.contains将不为true。存储Set<Integer>将有效。但是,重复的值将从集合中删除。
你的代码可以写成:

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<int[]> answers = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                int[] temp = {nums[i], nums[left], nums[right]};
                if (!contains(answers, temp)) {
                    answers.add(temp);
                }
                left++;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    List<List<Integer>> ans = new ArrayList<>();
    for (int[] oldAnswer : answers) {
        ans.add(List.of(oldAnswer[0], oldAnswer[1], oldAnswer[2]));
    }
    return ans;
}

private static boolean contains(List<int[]> answers, int[] answer) {
    for (int[] oldAnswer : answers) {
        if (Arrays.equals(answer, oldAnswer)) {
            return true;
        }
    }
    return false;
}

声明可以接近用法,对变量的内存使用没有影响。Continues也是一个风向标。
对于优化来说,第一件事是数据结构。拥有一个3个整数的列表不如一个int[3]数组好。你也可以使用这些值,并在整个循环中将它们保存在变量中。
另一个优化是有两个值,可以确定第三个查找的值。在排序数组中,* 二分搜索 * 将产生该索引(或-index-1,当没有找到插入位置时)。与在循环中向解决方案移动索引相比,这种二分搜索将大大加快算法的速度。
然后是对超出界限的候选人的捷径循环。也许没有实现100%,但足够。

public List<List<Integer>> threeSum2(int[] nums) {
    Arrays.sort(nums);
    List<int[]> answers = new ArrayList<>();
    for (int left = 0; left < nums.length - 2; left++) {
        int leftNum = nums[left];
        for (int mid = left + 1; mid < nums.length - 1; mid++) {
            int midNum = nums[mid];
            int soughtRightNum = -leftNum - midNum;
            if (soughtRightNum < midNum) {
                break;
            }
            int right = Arrays.binarySearch(nums, mid + 1, nums.length, soughtRightNum);
            if (right >= 0) { // Fpund.
                int[] ans = {left, mid, right};
                if (!contains(answers, ans)) {
                    answers.add(ans);
                }
            }
        }
    }
    List<List<Integer>> ans = new ArrayList<>();
    for (int[] oldAnswer : answers) {
        ans.add(List.of(oldAnswer[0], oldAnswer[1], oldAnswer[2]));
    }
    return ans;
}

Contains check和adding best是一起做的,如果答案真的很多,比如有一千个0,那也需要考虑一下,Set可能是个好主意。

相关问题