请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

【每日一题】Leetcode - 15. 3Sum

2023-07-13

Question

Leetcode - 15. 3Sum

Train of thought

The first we would like to resolve it by violent method, like this:

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        result.add(Arrays.asList(new Integer[]{nums[i], nums[j], nums[k]}));
                    }
                }
            }
        }
        result = result.stream().distinct().collect(Collectors.toList());
        return result;
    }

}

在这里插入图片描述
Of course, it timed out~, we take some head to think about the code, we find that we know the third number if we know the first and the second number, and we know that the array has sorted, so we can using binary search to find the third number, in order to make cost time lesser, we can also remember the numbers what we has be found.

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> result = new LinkedList<>();
        Set<String> ijkVisited = new HashSet<>();
        int nk;
        String key;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                nk = 0 - nums[i] - nums[j];
                key = nums[i] + "," + nums[j] + "," + nk;
                if (ijkVisited.contains(key)) {
                    continue;
                }
                if (Arrays.binarySearch(nums, j + 1, n, nk) >= 0) {
                    ijkVisited.add(key);
                    result.add(Arrays.asList(new Integer[]{nums[i], nums[j], nk}));    
                }
            }
        }
        return result;
    }

}

在这里插入图片描述

Optimize

  • the adjacent elements if equals, we can skip it;
  • we can reduce the range of third number maybe exists, because the array is sorted, if nums[first], nums[second] and nums[third] add result bigger than zero, needing find the third number who the position of second increase one, its exist range end with third position.
  • Break the second looping, if the variable of second position equals the variable of third position.
class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> result = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int k = n - 1;
            for (int j = i + 1; j < k; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                while (j < k && nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                }
                if (j == k) {
                    break;
                }
                if (nums[i] + nums[j] + nums[k] == 0) {
                    result.add(Arrays.asList(new Integer[]{nums[i], nums[j], nums[k]}));
                }
            }
        }
        return result;
    }

}

在这里插入图片描述

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部