2020-01-10 3Sum

2020-01-10  本文已影响0人  _伦_

不知道为什么注释掉do {right--;} while(right > 0 && nums[right] == nums[right + 1]);以及// do {left++;} while(left < nums.length && nums[left] == nums[left - 1]);,运行时间就从34ms降到24ms,从打败50%左右编程打败90%以上

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> results = new LinkedList<>();

        Arrays.sort(nums);

        for (int first = 0; first < nums.length - 2 && nums[first] <= 0; first++) {

            if (first == 0 || nums[first] != nums[first - 1]) {

                int left = first + 1, right = nums.length - 1;

                while (left < right) {

                    if (0 - nums[first] - nums[left] < nums[right])

                        // 为什么注释掉这句会快很多?

                        // do {right--;} while(right > 0 && nums[right] == nums[right + 1]);

                        right--;

                    else if (0 - nums[first] - nums[left] > nums[right])

                        // do {left++;} while(left < nums.length && nums[left] == nums[left - 1]);

                        left++;

                    else {

                        results.add(Arrays.asList(new Integer[]{nums[first], nums[left], nums[right]}));

                        do {left++;} while(left < nums.length && nums[left] == nums[left - 1]);

                        do {right--;} while(right > 0 && nums[right] == nums[right + 1]);

                    }

                }

            }

        }

        return results;

}

上一篇 下一篇

猜你喜欢

热点阅读