class Solution {
    public int subarraySum(int[] nums, int k) {
        // dp[j] 代表包括nums[j]后尽量接近k的子数组和，i为子数组的起始位置
        // dp[j] = nums[j] || dp[i] + nums[j]
        
        if (nums.length == 1 && nums[0] == k) return 1;
        else if (nums.length == 1 && nums[0] != k) return 0;

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int i = 0;
        int j = 1;
        int res = 0;
        // [0, 0], k = 0
        if (nums[i] == k) res++;
        for (; j < nums.length; j++) {
            // [1, 1, 1, 2, 3, 4, 5, 6], k = 7
            // [-1, -1, 1], k = 0
            while (i < j
            && ((dp[j - 1] + nums[j] > k && nums[i] > 0)
            || (dp[j - 1] + nums[j] < k && nums[i] < 0))) {
                dp[j - 1] -= nums[i++];
            }
            dp[j] = dp[j - 1] + nums[j];
            if (dp[j] == k) {
                res++;
            }
            // [0, 0], k = 0
            if (i != j && nums[j] == k) res++;
        }
        while (i > 0) {
            dp[j - 1] += nums[--i];
            if (dp[j - 1] == k) res++;
        }
        return res;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            // [-4, -1, -1, 0, 1, 2]
            if (nums[i] + nums[j] < 0) {
                int k = j - 1;
                while (k > i) {
                    if (nums[i] + nums[k] + nums[j] == 0) {
                        res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[k], nums[j])));
                        while (i < j && nums[i] == nums[i + 1]) i++;
                        break;
                    } else if (nums[i] + nums[k] + nums[j] > 0) {
                        k--;
                    } else {
                        break;
                    }
                }
                i++;
            }
            // [-1, -1, 0, 1, 2]
            else {
                int k = i + 1;
                while (k < j) {
                    if (nums[i] + nums[k] + nums[j] == 0) {
                        res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[k], nums[j])));
                        while (j > i && nums[j] == nums[j - 1]) j--;
                        break;
                    } else if (nums[i] + nums[k] + nums[j] > 0) {
                        break;
                    } else {
                        k++;
                    }
                }
                j--;
            }
        }
        return res;
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p == null || p.length() == 0) return new ArrayList<Integer>(0);
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        Set<Character> set1 = new HashSet<>();
        // p 使用set1存储，方便后续 O(1) 查找元素
        // p 是否有重复字符？
        for (char c : cp) {
            set1.add(c);
        }
        Set<Character> set2 = new HashSet<>();
        List<Integer> res = new ArrayList<>();
        // 滑动窗口，i记录窗口左边界，j为右边界，set2存储元素防止重复
        for (int i = 0, j = 0; i < cs.length && j < cs.length; j++) {
            // cs[j] 不是 p 包含的元素
            if (!set1.contains(cs[j])) {
                i = j + 1;
                set2.clear();
            } else {
                // cs[j] 是 p 包含的元素，添加到set2
                boolean b = set2.add(cs[j]);
                // 添加失败（已添加过）
                if (!b) {
                    while (cs[i] != cs[j]) {
                        set2.remove(cs[i++]);
                    }
                    i++;
                }
                // set2大小 === cp长度
                if (set2.size() == cp.length) {
                    res.add(i);
                    set2.remove(cs[i++]);
                }
            }
        }
        return res;
    }
}