经典例题

package org.example.algorithm.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 数组与双指针 — 经典题
 * <p>
 * 1. 两数之和 II（有序） LeetCode 167
 * 2. 盛最多水的容器     LeetCode 11
 * 3. 无重复字符的最长子串 LeetCode 3
 */
public class ArrayProblems {

    /**
     * 题意：有序数组中找两数之和 = target，返回 1-based 下标。
     * 思路：对撞指针，sum 小则 L++，大则 R--。
     * 复杂度：O(n) 时间，O(1) 空间。
     * 易错：下标从 1 开始；不要用 HashMap 忘了「有序」条件。
     */
    public int[] twoSum(int[] numbers, int target) {
        int L = 0, R = numbers.length - 1;
        while (L < R) {
            int sum = numbers[L] + numbers[R];
            if (sum == target) {
                return new int[]{L + 1, R + 1};
            } else if (sum < target) {
                L++;
            } else {
                R--;
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 题意：两条竖线与 x 轴构成容器，求最大盛水量。
     * 思路：对撞；面积 = min(h[L],h[R]) * (R-L)。
     *       移动较矮的一边（高的不动，宽变小只会更差或不变）。
     * 复杂度：O(n) / O(1)
     * 易错：先算面积再移动；两边等高时可任意移一边或两边都移。
     */
    public int maxArea(int[] height) {
        int L = 0, R = height.length - 1, ans = 0;
        while (L < R) {
            int h = Math.min(height[L], height[R]);
            ans = Math.max(ans, h * (R - L));
            if (height[L] < height[R]) {
                L++;
            } else {
                R--;
            }
        }
        return ans;
    }

    /**
     * 题意：字符串中最长无重复字符子串的长度。
     * 思路：滑动窗口 + 字符上次出现位置；遇重复则 left 跳到重复字符后。
     * 复杂度：O(n) / O(Σ) 字符集
     * 易错：left 只能右移（Math.max）；字符可用 map 或 int[128]。
     */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, ans = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last.containsKey(c)) {
                left = Math.max(left, last.get(c) + 1);
            }
            last.put(c, right);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        ArrayProblems p = new ArrayProblems();

        System.out.println("=== 167 两数之和 II ===");
        System.out.println(Arrays.toString(p.twoSum(new int[]{2, 7, 11, 15}, 9)));
        // 期望 [1, 2]

        System.out.println("=== 11 盛水容器 ===");
        System.out.println(p.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
        // 期望 49

        System.out.println("=== 3 无重复最长子串 ===");
        System.out.println(p.lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(p.lengthOfLongestSubstring("bbbbb"));    // 1
        System.out.println(p.lengthOfLongestSubstring("pwwkew"));   // 3
    }
}