双指针

DoublePointer

相向双指针

public class L167 {

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        System.out.println(Arrays.toString(twoSum(nums, 9)));
    }

    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        int sum;
        while (left < right) {
            sum = numbers[left] + numbers[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return new int[]{left + 1, right + 1};
            }
        }
        return null;
    }
}

public class L15 {

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(nums));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        int sum;
        for (int i = 0; i < len; i++) {
            int left = i + 1;
            int right = len - 1;
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right) {
                        if (nums[left] == nums[left - 1]) {
                            left++;
                        } else {
                            break;
                        }
                    }
                    while (left < right) {
                        if (nums[right] == nums[right + 1]) {
                            right--;
                        } else {
                            break;
                        }
                    }
                } else if (sum < 0){
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
}

• 将中间部分看成是第 i 个

public class L42 {

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(height));
    }

    public static int trap(int[] height) {
        int preMax = 0;
        int sufMax = 0;
        int left = 0;
        int right = height.length - 1;
        int res = 0;
        while (left < right) {
            preMax = Math.max(height[left], preMax);
            sufMax = Math.max(height[right], sufMax);

            if (preMax < sufMax) {
                res += preMax - height[left];
                left++;
            } else {
                res += sufMax - height[right];
                right--;
            }
        }
        return res;
    }

}

同向双指针

public class L209 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        System.out.println(minSubArrayLen(7, nums));
    }

    /**
     * 右指针一直向右移动，若找到长度满足 target 的子数组，则左指针向前移动
     *
     * @param target target
     * @param nums nums
     * @return res
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int len = nums.length;
        int res = len + 1;
        for (int right = 0; right < len; right++) {
            sum += nums[right];
            while (sum - nums[left] >= target) {
                sum -= nums[left];
                left++;
            }
            if (sum >= target) {
                res = Math.min(res, right - left + 1);
            }
        }
        return res > len ? 0 : res;
    }

}

public class L713 {

    public static void main(String[] args) {
        int[] nums = {10, 5, 2, 6};
        System.out.println(numSubarrayProductLessThanK(nums, 100));
    }

    /**
     * 同向双指针
     *
     * @param nums nums
     * @param k k
     * @return res
     */
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 1;
        int res = 0;
        int len = nums.length;
        while (right < len) {
            sum *= nums[right];
            while (sum >= k) {
                sum /= nums[left];
                left++;
            }
            res += right - left + 1;
            right++;
        }
        return res;
    }
}

public class L3 {

    public static void main(String[] args) {
        L3 s = new L3();
        System.out.println(s.lengthOfLongestSubstring("pwwkew"));
    }

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int res = 0;
        Set<Character> set = new HashSet<>();
        int left = 0;
        int right = 0;
        while (right < len) {
            if(!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
            } else {
                set.remove(s.charAt(left));
                left++;
            }
            res = Math.max(set.size(), res);
        }
        return res;
    }
}

快慢指针