双指针

leetcode209】长度最小的子数组

public class MinSubArrayLen {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int minlen = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int sum = 0;
        int length = nums.length;
        while (end < length) {
            sum += nums[end++];
            while (sum >= s) {
                minlen = (end - start) < minlen ? (end - start) : minlen;
                sum -= nums[start++];
            }
        }

        return minlen == Integer.MAX_VALUE ? 0 : minlen;
    }
}

leetcode15. 三数之和

排序   加 双指针。在遍历的过程中注意减枝和去重

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //减枝
            if (nums[i] > 0) {
                break;
            }
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int start = i + 1;
            int end = nums.length - 1;
            while (start < end) {
                if (nums[start] + nums[end] + nums[i] < 0 || (start > i + 1 && nums[start] == nums[start - 1])) {
                    start++;
                } else {
                    if (nums[start] + nums[end] + nums[i] > 0 || (end < nums.length - 1 && nums[end] == nums[end + 1])) {
                        end--;
                    } else {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[start++]);
                        list.add(nums[end--]);
                        result.add(list);
                    }
                }
            }
        }
        return result;
    }

leetcode 16. 最接近的三数之和

public int threeSumClosest(int[] nums, int target) {
        assert nums.length > 2;
        Arrays.sort(nums);
        int left;  
        int right;
        int sum3;  //数组中的三个数的和
        int res = 0;  //记录返回结果
        int tmp = Integer.MAX_VALUE; //记录sum3和target的差的绝对值
        for (int i = 0; i < nums.length - 2; i++) {
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                sum3 = nums[left] + nums[right] + nums[i];
                //如果已经找到等于target的三个数，直接返回即可。
                if(sum3 == target){
                    return target;
                }
                if (Math.abs(sum3 - target) < tmp) {
                    tmp = Math.abs(sum3 - target);
                    res = sum3;
                }
                if (sum3 > target) {
                    right--;
                } else {
                    left++;
                }
            }

        }

        return res;
    }