259. 3Sum Smaller

二刷 06/2022

Version #1 Two Pointers

写了一个bug就是以为nums[i] >  target就可以终止，但是实际上如果nums[i]是负数，那么再加上一个比它略大的负数，sum还是可以继续变小的

所以正确的判断是nums[i] > 0 && nums[i] >= target再停止

Time O(N^2)

Space O(1)

Runtime: 6 ms, faster than 97.74% of Java online submissions for 3Sum Smaller.

Memory Usage: 43.3 MB, less than 46.03% of Java online submissions for 3Sum Smaller.

class Solution {

    public int threeSumSmaller(int[] nums, int target) {

        //  1 2 3 4 5

        //  l       r

        // when we are seeing that nums[l] + nums[r] < target, we know for current l pointer, all indicies between (i, j] could sum up to a smaller than target number

        // so that we add (j - i) to the final result and increment l pointer by 1

        Arrays.sort(nums);

        int cnt = 0;

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] > 0 && nums[i] >= target) {

                return cnt;

            }

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

            while (left < right) {

                if (nums[i] + nums[left] + nums[right] < target) {

                    cnt += right - left;

                    left++;

                } else {

                    right--;

                }

            }

        }

        return cnt;

    }

}

一刷

Version #1 Two Pointer
Time O(n^2)

在two pointer的时候，如果以左指针为判断条件，left++的话，终止条件是sum >= target是一个不符合的条件，就很容易写错
相反以right指针向左扫，停下的时候就是符合条件的，所以就是正确的
(left, right]都是right的valid值
一共有right - left个

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int count = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                while (left < right && nums[i] + nums[left] + nums[right] >= target) {
                    right--;
                }
                count += right - left;
                //   i l   r
                // [-2,0,1,3]
                left++;
            }
        }
        return count;
    }
}