209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

思路: 双指针来做, 找到window的sum >= s的最小的window长度。用Left跟Right两个指针分别表示window的左边界跟右边界。新来一个数,如果sum>=s,则记录当前最小的窗口长度minLen=min(minLen,right-left), 并将left左边界右移;如果sum<s, 则需要扩大window边界,将右边界右移。 注意循环的条件: right<=left && right <nums.length; 注意最后比较minLen跟num.length, 注意退出条件,当right移到最右侧的时候,还要移动左边界往右移,缩小window长度
,来看是否有更优解法.
复杂度: Time O(n), Space: O(1)

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int left = 0, right = 0, minLen = Integer.MAX_VALUE, sum = 0;
        while(left <= right && right < nums.length) {
            if (sum < s) { // sum of window less than s
                if (right < nums.length) {
                    sum = sum + nums[right];
                }
                right++;
            } else { // sum of window greater equal than s
                int windowLen = right - left;
                minLen = Math.min(minLen, windowLen);
                sum = sum - nums[left];
                left++;
            }
        }
        return minLen < nums.length ? minLen : 0;
    }
}

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

rainwatertrap

 思路: 两指针方法,我们可以用两个指针,一个从左边往右边遍历,另一个从右边往左边遍历。先找到左右两边的第一个峰值作为参照位, 当从左往右遍历的时候,如果左指针找到的值比左边峰值小,就表示可以盛水,取他们的差值放到结果。 从右往左遍历的时候,如果右指针找到的值比右边峰值小,就把他们的差值放到结果。 难点在于,当两个峰值临近的时候,我们要取那个比较小的峰值来计算结果,因为积水区间是按较小的计算,所以我们在左右指针遍历之前要判断哪个比较小,就算哪个。

public class Solution {
    public int trap(int[] height) {
        if (height.length < 3 || height == null) 
            return 0;
        int sum = 0;
        int left = 0, right = height.length - 1;
        while(left < right && height[left] < height[left + 1]) left++; // find the first peek from left side
        while(left < right && height[right] < height[right - 1]) right--; // find the first peek from right side
        while(left < right) {
            int leftPeekVal = height[left];
            int rightPeekVal = height[right];
            //如果左边峰值较小,先计算左边
            if (leftPeekVal < rightPeekVal) {
                while(left < right && height[++left] < leftPeekVal) {
                    sum += leftPeekVal - height[left];
                }
            } else {
                while(left < right && height[--right] < rightPeekVal) {
                    sum += rightPeekVal - height[right];
                }

            }
        }
        return sum;

    }
}

259. 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]
Follow up:
Could you solve it in O(n2) runtime?

思路: 3Sum的变种,要求统计三个数的和小于给定target的次数。先排序,然后用外层循环来确定第一个数, 内层循环用左右指针从两头往中间寻找。得到三个数的和,如果和大于等于target,说明找大了, right指针往左移动;如果找到的和小于target,我们取right-left的差值即为有效结果。 为什么呢? 假设left不动,那那么right像左移,直到重合之前的前一点都属于有效结果。

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length < 3) return 0;
        Arrays.sort(nums);
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            int first = nums[i];    
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = first + nums[left] + nums[right];
                if (sum < target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }
}

16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路: 3Sum的变种, 要找离target最近的三个数的和。 跟3Sum一样这道题需要注意duplicate的处理。 先Sort下给定数组,Time为O(nlogn), 我们可以用2个全局变量一个是minNum来记录得到的sum跟target的绝对值之差,还有一个closet用来记录sum。

public class Solution {
    public int threeSumClosest(int[] nums, int target) {

        if(nums.length &lt; 3 || nums == null) return 0;
        Arrays.sort(nums);
        int closet = 0;
        int minNum = Integer.MAX_VALUE;
        for(int i = 0; i &lt; nums.length; i++) {
            if (i != 0 &amp;&amp; nums[i] == nums[i - 1]) 
                continue;  // skip duplicates
            int fixed = nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while (left &lt; right) {
                int sum = fixed + nums[left] + nums[right];
                if (Math.abs(sum - target) &lt; minNum) {
                    minNum = Math.abs(sum - target);
                    closet = sum;
                }
                if (sum &lt; target) {
                    left++;
                } else  {
                    right--;
                }

            }


        }
        return closet;

    }
}