class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) return new int[]{map.get(need), i};
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

class Solution {
    int ans=0;
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int len=1;
            while(set.contains(++x)) len++;
            ans = Math.max(ans, len);
        }
        return ans;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int pos=0;
        for(int x:nums){
            if(x!=0) nums[pos++]=x;
        }
        //注意这个api是左闭右开
        Arrays.fill(nums,pos,nums.length,0);
    }
}

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, ans = 0;
        while (l < r) {
            ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
            if (height[l] < height[r]) l++;
            else r--;
        }
        return ans;
    }
}

class Solution {
    List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            //去重
            if(i>=1&&nums[i]==nums[i-1]) continue;
            int l=i+1, r=nums.length-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum>0) r--;
                else if(sum<0) l++;
                else {
                    ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while(l<r&&nums[l]==nums[l+1]) l++;
                    while(l<r&&nums[r-1]==nums[r]) r--;
                    l++;
                    // 1 2 2 2 3 4 5 跳到3
                        r--;
                        //到相等的最后一个, 然后跳到不同的下一个
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int lMax = 0, rMax = 0, ans = 0;
        while (l < r) {
            lMax = Math.max(lMax, height[l]);
            rMax = Math.max(rMax, height[r]);
            if (lMax < rMax) ans += lMax - height[l++];
            else ans += rMax - height[r--];
        }
        return ans;
    }
}
3 2 5
lmax=3,rmax=5, ans+=lmax-nums[l++]=3-3;
lmax=3,rmax=5, ans+=lmax-nums[l++]=3-2;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] cnt = new int[128];
        int l = 0, ans = 0;
        for (int r = 0; r < s.length(); r++) {
            cnt[s.charAt(r)]++;
            while (cnt[s.charAt(r)] > 1) cnt[s.charAt(l++)]--;
            ans = Math.max(ans, r - l + 1);
            /*注意别写成
                while(++cnt[s.charAt(r)]>1){
                    cnt[s.charAt(l++)]--;
                }
                因为while每次都会判断, 每次都给++cnt(r)
            */
        }
        return ans;
    }
}

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> findAnagrams(String s, String p) {
        int[] standard = new int[128], cur=new int[128];
        for(char ch:p.toCharArray()) standard[ch]++;
        int l=0, len=p.length();
        for(int r=0;r<s.length();r++){
            cur[s.charAt(r)]++;
            //len-1是刚好满足程度的, len就超出1个
            if(r>=len) cur[s.charAt(r-len)]--;
            if(r>=len-1&&Arrays.equals(standard,cur)) ans.add(r-len+1);
        }
        return ans;
    }
}

class Solution {
        int ans=0;
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        //空前缀出现一次
        //别用前缀和数组, 下标麻烦
        /* presum[i] 表示 nums 前 i 个元素之和
        int[] presum = new int[n + 1];
            for (int i = 1; i <= n; i++) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }*/
        int sum = 0;
        for (int x : nums) {
            sum += x;
            ans += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int pos=0;
        int[] ans=new int[nums.length-k+1];
        Deque<Integer> deq=new ArrayDeque<>();
        for(int i=0;i<nums.length;i++){
            //弹出窗口外的
            while(!deq.isEmpty()&&deq.peekFirst()<=i-k) deq.pollFirst();
            //将队列按从大到小排
            while(!deq.isEmpty()&&nums[i]>=nums[deq.peekLast()]) deq.pollLast();
            //加入当前
            deq.addLast(i);
            if(i>=k-1){
                ans[pos++]=nums[deq.peekFirst()];
                //注意ans装的是数, 非位
            }
        }
        return ans;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if(s.length()<t.length()) return "";
        //统计目标串的词频, 用负数表示
        int[] cnt=new int[256];
        for(char c:t.toCharArray()) cnt[c]--;
        int l=0,start=0,debt=t.length(),minlen=Integer.MAX_VALUE;
        for(int r=0;r<s.length();r++){
        //如果++后<=0, 说明是目标, 则--debt
            if(++cnt[s.charAt(r)]<=0) debt--;
            
            while(debt==0){
                if(r-l+1<=minlen){
                    start=l;
                    minlen=r-l+1;
                }
        //如果--后<0, 说明是目标, 因为不是目标串应该--后>=0
                if(--cnt[s.charAt(l++)]<0) debt++;
            }
            
        }
        return minlen==Integer.MAX_VALUE?"":s.substring(start,start+minlen);
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], ans = nums[0];
        //不能设0, 因为如果[-1], 他不会选, 题目又说要至少一个元素
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
	    var ans = new ArrayList<int[]>();
        //按第一个数从小到大排
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        for(int[] cur:intervals){
            //当前答案是空or两个数组尾首不相接
        if(ans.isEmpty()||ans.get(ans.size()-1)[1]<cur[0]){
                ans.add(cur);
            }else ans.get(ans.size()-1)[1]=Math.max(ans.get(ans.size()-1)[1],cur[1]);
        }
        return ans.toArray(new int[0][]);
        //注意这个写法!
    }
}

ArrayList<int[]> list = new ArrayList<>();
// ... 添加元素
int[][] result = list.toArray(new int[0][]);

ArrayList<int[]> list = new ArrayList<>();
list.add(new int[]{1, 2});
list.add(new int[]{3, 4, 5});
int[][] result = list.toArray(new int[0][]);
// result = [[1, 2], [3, 4, 5]]

class Solution {
    //非常厉害的思维
    public void rotate(int[] nums, int k) {
        //k可能大于长度nums.length;
        k%=nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }
    public void reverse(int[] nums,int l,int r){
        while(l<r){
            int tmp=nums[l];
            nums[l++]=nums[r];
            nums[r--]=tmp;
        }
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len=nums.length;
        int[] pre=new int[len]; pre[0]=1;
        for(int i=1;i<len;i++){
            pre[i]=pre[i-1]*nums[i-1];
        }
        //自己写一下前缀和数组和后缀和数组, 即知道累积规则
        int suffix=1;
        for(int i=len-1;i>=0;i--){
            pre[i]*=suffix;
            suffix*=nums[i];
        }
        return pre;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len=nums.length;
        for(int i=0;i<len;i++){
            //发现属于[1~n]的数并且nums\[x-1]=x
            while(1<=nums[i]&&nums[i]<=len&&nums[nums[i]-1]!=nums[i]){
                int tmp=nums[nums[i]-1];
                nums[nums[i]-1]=nums[i];
                nums[i]=tmp;
            }
        }
        //再遍历一遍(pos,val)!=(i-1,nums[i])
        for(int i=0;i<len;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return len+1;
        //所有学生都在对的位置, [1,2]->3
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if (row0) Arrays.fill(matrix[0], 0);
        if (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int l=0,r=matrix[0].length-1;
        int top=0,bot=matrix.length-1;
        while(l<=r&&top<=bot){
            for(int i=l;i<=r;i++){
                ans.add(matrix[top][i]);
            }
            top++;
            
            for(int i=top;i<=bot;i++){
                ans.add(matrix[i][r]);
            }
            r--;
            
            //检查边界, 如果这个不符合, 下一个也肯定符合
            //否则下一轮while循环结束, 也即到达最中心一点
            if(top<=bot){
                for(int i=r;i>=l;i--){
                    ans.add(matrix[bot][i]);
                }
                bot--;
            }
            if(l<=r){
                for(int i=bot;i>=top;i--){
                    ans.add(matrix[i][l]);
                }
                l++;
            }
        }
        return ans;
    }
}

class Solution {
    public void rotate(int[][] matrix) {
        //本题本质就是对角线交换+左右反转
        int rows=matrix.length, cols=matrix[0].length;
        for(int i=0;i<rows;i++){
            //注意这里只需要到对角线就行了
            for(int j=0;j<i;j++){
                if(i==j) continue;
                int tmp = matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=tmp;
            }
        }
        for(int[] row:matrix){
            int l=0,r=cols-1;
            while(l<r){
                int tmp=row[l];
                row[l++]=row[r];
                row[r--]=tmp;
            }
        }
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}
 // - matrix[i][j] > target → 当前数太大，只能往左走（往下会更大）
 // - matrix[i][j] < target → 当前数太小，只能往下走（往左会更小）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
	        //注意这里是等于null才变向
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
        //or b
    }
}

a:x
b:y
公共:z
a: x z y z
b: y z x z

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null,cur=head;
        while(cur!=null){
            //先保住下一个, 再转向
            ListNode nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转前半段到slow正好
        ListNode pre=null;
        while(head!=slow){
            ListNode nxt=head.next;
            head.next=pre;
            pre=head;
            head=nxt;
        }
        slow= fast==null?slow:slow.next;
        while(slow!=null){
            if(slow.val!=pre.val) return false;
            //注意别忘记走
            slow=slow.next;
            pre=pre.next;
        }
        return true;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
            //如果有环必定相遇的!!!!!!!!!!!!!!!!!!!1
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //slow=b=(kc-a), fast=2b
        //fast-slow=kc--> b=kc-a-->差a到kc完整的圆!
        //head到入环口也是a, 所以while(slow!=head)
        ListNode fast=head, slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            //有环必相遇
            if(fast==slow){
	            //相遇则此时head和slow齐步走, 必定到环口
                while(slow!=head){
                    slow=slow.next;
                    head=head.next;
                }
                return slow;
            }
        }
        return null;
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy=new ListNode(0),cur=dummy;
        ListNode p1=list1,p2=list2;
        while(p1!=null && p2!=null){
            if(p1.val<=p2.val){
                cur.next=p1;
                p1=p1.next;
            }else {
                cur.next=p2;
                p2=p2.next;
            }
            cur=cur.next;
        }
        cur.next= p1==null?p2:p1;
        return dummy.next;
    }
    }

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy=new ListNode(0), cur=dummy;
        int carry=0,sum=0;
        while(l1!=null||l2!=null||carry!=0){
            //这里主要要加上上一位的进位!!!!!!!!!
            sum=getVal(l1)+getVal(l2)+carry;
            carry=sum/10;
            cur.next=new ListNode(sum%10);
            cur=cur.next;
            l1=l1==null?null:l1.next;
            l2=l2==null?null:l2.next;
        }
        return dummy.next;
    }
    public int getVal(ListNode p){
        return p==null?0:p.val;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n; i++) fast = fast.next;
        //注意这里是刚好走到最后一个节点, fast!=null则是走到最后一个节点的下一个
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0,head);
        ListNode node0=dummy, node1=head;
        while(node1!=null&&node1.next!=null){
            ListNode node2=node1.next;
            ListNode node3=node2.next;
            //改签
            node0.next=node2;
            node2.next=node1;
            node1.next=node3;
            
            //更新好下一轮
            node0=node1;
            node1=node3;
        }
        return dummy.next;
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //计算总长度, 好控制循环次数
        int len=0;
        ListNode cur=head;
        while(cur!=null){ cur=cur.next; len++;}
        ListNode dummy=new ListNode(0,head);
        ListNode p0=dummy, pre=null;
        cur=head;
        
        while(len>=k){
            ListNode pre = null;  // 移到这里，每轮重置
            for(int i=0;i<k;i++){
                ListNode nxt=cur.next;
                cur.next=pre;
                pre=cur;
                cur=nxt;
            }
            //标记链表的尾巴
            ListNode nxt=p0.next;
            //连接链表的首
            p0.next=pre;
            //尾连下一条首
            nxt.next=cur;
            //继续下一轮
            p0=nxt;
            len-=k;
        }
        return dummy.next;
    }
}