public List<List<String>> groupAnagrams(String[] strs) {
        
        Map<String, List<String>> map = new HashMap();
        for (int i = 0; i < strs.length; i++) {
            char[] array = strs[i].toCharArray();
            Arrays.sort(array);
            List<String> list = map.containsKey(new String(array)) ? map.get(new String(array)) : new ArrayList();
            list.add(strs[i]);
            map.put(new String(array), list);
        }
      
        return new ArrayList<>(map.values());
    }

    public int lengthOfLongestSubstring(String s) {
        char[] array = s.toCharArray();
        int left = -1,max = 0;
        Map<Character, Integer> map = new HashMap();
        for(int i = 0; i < array.length; i++){
            //以i为右指针 更新查找满足无重复的子串左指针
            if(map.containsKey(array[i])){
               left = Math.max(left, map.get(array[i]));
            }
            map.put(array[i], i);
            max = Math.max(max, i - left);
        }
        return max;
    }

      // 选定一个数 剩下的数字按照左右指针去寻找
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList();
        for (int i = 0; i < nums.length - 2; i++) {
            // 重要的是剪枝
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0)
                break;// 一定大于0场景
            if (i > 0 && nums[i] == nums[i - 1])
                continue; // 重复场景
            if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0)
                continue;// 加上最大的两个值都＜0场景 可以直接跳过
            // 设定两个双指针去寻找剩下的 两个值 这里就是两数之和了
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int res = nums[i] + nums[left] + nums[right];
                if (res > 0) {
                    right--;
                } else if (res < 0) {
                    left++;
                } else {
                    list.add(List.of(nums[i], nums[left], nums[right]));
                    // 重复场景剪枝
                    for (left++; left < right && nums[left - 1] == nums[left]; left++)
                        ;
                    for (right--; left < right && nums[right + 1] == nums[right]; right--)
                        ;
                }
            }
        }
        return list;
    }

 List<String> ans = new ArrayList();
    StringBuilder str = new StringBuilder();
     Map<Character, String> map = new HashMap();
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return ans;
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        dfs(0, digits);
        return ans;

    }

    private void dfs(int index, String digits){
        if(index == digits.length()){
            ans.add(str.toString());
            return;
        }
        char it = digits.charAt(index);
        String all = map.get(it);
        for(int i = 0; i < all.length(); i++){
            str.append(all.charAt(i));
            dfs(index + 1, digits);
            str.deleteCharAt(index);
        }
    }

               long last = Long.MIN_VALUE;
                // 1.递归
                if(root == null) return true;
                boolean left = isValidBSI(root.left);
                if(last >= root.val)return false;
                key = root.val;
                boolean right = isValidBSI(root.right);
                return left && right;


      // 2.中序遍历 保证数组递增 深度优先用栈或者递归 一般栈都会换双端队列
        Deque<TreeNode> deque = new ArrayDeque();
        while (root != null || !deque.isEmpty()) {
            if (root != null) {
                deque.push(root);
                root = root.left;
            } else {
               TreeNode poll = deque.poll();
                if (last >= poll.val) {
                    return false;
                }
                last = poll.val;
                root = poll.right;
            }
        }
        return true;

   public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0 && i > left){
                nums[i] = nums[left];
                nums[left] = 0;
                left++;
                i--;//这一步是为了保证换过来的数字要再判断一遍
            }

            if(nums[i] == 2 && i < right){
                nums[i] = nums[right];
                nums[right] = 2;
                right--;
                i--;
            }
        }
    }