01相向双指针

        两数之和Ⅱ：

        给你一个下标从1开始的整数数组numbers[] ，该数组已按非递减顺序排
列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是numbers[indexi] 和numbers[index2]]，则 1 <=index1 < index2 <= numbers.length 。

        输入:numbers = [2,7,11,15]， target = 9
        输出：[1,2]
        解释：2与7 之和等于目标数 9。因此 index1 =1，index2
        2。返回[1，2]

public int[] twoSum(int[] numbers, int target) {
        //只针对排序数组   题目中已经是递增
        int i = 0;
        int j = numbers.length-1;
        while(i<j){    //== 不满足条件
            int sum = numbers[i]+numbers[j];
            if(sum>target) j--;
            else if(sum<target) i++;
            else 
                return new int[]{ i+1,j+1 };
        }
        return new int[0];  //不满足返回0
    }

        三数之和

        给你一个整数数组nums]，判断是否存在三元组[nums[i]，nums[j],nums [k]] 满足i!= j]、[i!= k 且j!= k ，同时还满足nums[i]+nums[j]+ nums[k]」==0。请你返回所有和为且不重复的三元组

        输入:nums = [-1,0,1,2,-1,-4]
        输出：[[-1,-1,2],[-1,0,1]]
        解释：
        nums[0] + nums[1]1+ nums[2]=（-1）+ 0+ 1 = 0
        nums[1]1 + nums[2]1+ nums[4]= 0 +1+（-1）= 0
        nums[0] + nums[3]1+ nums[4] =（-1）+ 2+（-1)）=0
        不同的三元组是[-1,0,1］ 和 [-1,-1,2]

public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i > 0 && x == nums[i - 1]) 
                continue; // 跳过重复数字
            if (x + nums[i + 1] + nums[i + 2] > 0) 
                break;    //当三个最小的数相加大于0 后面的操作都可以省略
            if (x + nums[n - 2] + nums[n - 1] < 0) 
                continue; //当最大的两个数加上x都小于0 说明x太小了
            
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) {
                    k--;
                } else if (s < 0) {
                    j++;
                } else {
                    //List.of(1,2,null)  和Arrays.asList(1, 2, null)
                    //前者不能修改 后者则可以能
                    ans.add(List.of(x, nums[j], nums[k])); 
                    //初始条件不能少，否则会越界  逻辑就是 发现一组满足条件之后
                    //j向右移动一个单位并和上一个数据比较
                    //k向左移动一个单位并和上一个数据比较
                    for (j++; j < k && nums[j] == nums[j - 1]; j++); // j++ 跳过重复数字
                    for (k--; k > j && nums[k] == nums[k + 1]; k--); // k-- 跳过重复数字
                }
            }
        }
        return ans;
    }

02相向双指针

        盛最多水的容器

                给定一个长度为n 的整数数组height。有n 条垂线，第i 条线的两个端点是（i，0）和（i，height[i]）找出其中的两条线，使得它们与×轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

public int maxArea(int[] height){
    int ans = 0;
    int i = 0;
    int j = height.length-1;
    while(i<j){
        int v = (j-i)*Math.min(height[i],height[j]);
        ans = Math.max(ans,v);
        //存在三种情况   左边柱子 更长，更短，一样长
        // 短的抛弃，寻找可能更长的
        if(height[i]>height[j])
            j--;
        else 
            i++;
    } 
    return ans;
}

        接雨水

        给定n 个非负整数表示每个宽度为1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

        输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
        输出：6
        解释：上面是由数组且[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接6个单位的雨水(蓝色部分表示雨水)

public int trap(int[] height) {
        int ans = 0;
        int left = 0;
        int right = height.length - 1;
        int preMax = 0; // 前缀最大值，表示从左到右遍历时的最大高度
        int sufMax = 0; // 后缀最大值，表示从右到左遍历时的最大高度
        while (left < right) {    
            //帮助理解：假设当前是第四个位置  所装的水取决于左侧和右侧得最小高度 再减去柱子高度
            //桶壁高度随left的增加 而取最大值，实现更新
            preMax = Math.max(preMax, height[left]);
            sufMax = Math.max(sufMax, height[right]);
            //取二者之间的较小值
            ans += preMax < sufMax ? preMax - height[left++] : sufMax - height[right--];
        }
        return ans;    
    }

03滑动窗口

        长度最小的子数组

                给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl,numsl+1,numsr-1，numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。
                示例1:
                输入：target = 7，nums=[2,3,1,2,4,3]
                输出：2
                解释：子数组[4,3]是该条件下的长度最小的子数组。

public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = n + 1;
        int sum = 0; 
        int left = 0; 
        // 枚举子数组右端点
        for (int right = 0; right < n; right++) {     
            //窗口向右边拓展
            sum += nums[right];
            //假如左边的数删去之后还满足窗口条件  
            while (sum - nums[left] >= target) { 
                sum -= nums[left]; 
                left++;
            }
            //更新窗口长度
            if (sum >= target) {
                ans = Math.min(ans, right - left + 1);
            }
        }
        return ans <= n ? ans : 0;
    }

        乘积小于K的子数组

                给你一个整数数组nums和一个整数k，请你返回子数组内所有元素的乘积严格小于k的连续子数组的数目。
                示例1:
                输入:nums = [10,5,2,6]，k = 100
                输出：8
                解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
                需要注意的是是[10,5,2］并不是乘积小于 100的子数组。

public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        if (k <= 1)  return 0;
        for (int i = 0, j = 0, cur = 1; i < n; i++) {
            cur *= nums[i];
            while (cur >= k)
                cur /= nums[j++];
            /*为什么是i-j+1?
            *假设当前窗口的左端点是」，右端点是i，且窗口内的乘积只cur<k，那么以nums[i]为结
            *尾的合法子数组的左端点可以是j到i之间的任意一个位置，包括j和i。
            *·例如：
            *如果j=２，i=5，那么以，nums[5]为结尾的合法子数组的左端点可以是2,3,4,
            *5，共5-2+1=4 个。
            *因此，i-j+1表示从j到i之间的所有可能的左端点个数，即以nums[i]为结尾的合法子
            *数组的个数。*/
            ans += i - j + 1;
        }
        return ans;
    }

        无重复字符的最长子串

                给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
                示例1:
                输入：s = "abcabcbb"
                输出：3
                解释：因为无重复字符的最长子串是'abc",所以其长度为3。

public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int i=-1;  
        int ans=0;
        for(int j=0;j<s.length();j++){
            //i是左端   j是右端
            //map记录上次出现的位置
            if(map.containsKey(s.charAt(j))){
                i = Math.max(i,map.get(s.charAt(j)));
            }
            //j - i是距离长度
            ans = Math.max(ans,j-i);
            map.put(s.charAt(j),j);
        }
        return ans;
    }

        

04 二分查找

        在排序数组中查找元素的第一个和最后一个位置

                 给你一个按照非递减顺序排列的整数数组且nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值直target，返回[-1，-1]。你必须设计并实现时间复杂度为o（logn）的算法解决此问题。
                示例1:
                输入:nums = [5,7,7,8,8,10]]， target = 8
                输出：[3,4]

        解析：

• 循环结束时，left 和 right 会满足 left = right + 1。

• 这是因为每次循环都会将查找区间缩小一半，直到区间为空，即 left 和 right 相邻

• left 和 right 相邻，即 left = right + 1。

• right 指向的是最后一个小于 target 的元素的下标，因此 nums[right] < target。

• left 指向的是第一个大于等于 target 的元素的下标，因此 nums[left] >= target

public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1}; 
        }
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }
    
    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 闭区间 [left, right]
        while (left <= right) {      // 区间不为空
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1; // 范围缩小到 [left, mid-1]
            } else {
                left = mid + 1; // 范围缩小到 [mid+1, right]
            }
        }
        // 循环结束后 left = right+1
        // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }
    
    private int lowerBound2(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 左闭右开区间 [left, right)
        while (left < right) {   // 区间不为空
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 范围缩小到 [left, mid)
            } else {
                left = mid + 1; // 范围缩小到 [mid+1, right)
            }
        }
        // 循环结束后 left = right
        // 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }

    private int lowerBound3(int[] nums, int target) {
        int left = -1;
        int right = nums.length;    // 开区间 (left, right)
        while (left + 1 < right) {  // 区间不为空
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        // 循环结束后 left+1 = right
        // 此时 nums[left] < target 而 nums[right] >= target
        // 所以 right 就是第一个 >= target 的元素下标
        return right;
    }

05二分查找（O() = logn）

        寻找峰值

                峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums，找到峰值元素并返回其索引i。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
                示例1:
                输入：nums =[1,2,3,1]
                输出：2
                解释：3是峰值元素，你的函数应该返回其索引2。

public int findPeakElement(int[] nums) {
        //红蓝染色法  
        int left = 0;
        int right = nums.length-1;
        while(left < right){  //[left,right)
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }