【leetcode刷题记录】（java）数组 链表 哈希表

四、题目之：代码随想录

https://programmercarl.com/

(1) 代码随想录：数组

704. 二分查找

class Solution {public int search(int[] nums, int target) {if(target<nums[0] || target>nums[nums.length-1]){return -1;}int left = 0,right = nums.length-1;while(left<=right){int mid = left + (right-left)/2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){right = mid-1;}else{left = mid+1;}}return -1;}
}

27. 移除元素

暴力解:

class Solution {public int removeElement(int[] nums, int val) {int n=nums.length;for(int i = 0; i < n; i++){if(nums[i] == val){for(int j = i+1; j < n; j++){nums[j-1] = nums[j];}i--;//注意这里的更新n--;}}return n;}
}

双指针：

class Solution {public int removeElement(int[] nums, int val) {// 快慢指针int slowIndex = 0;//基本思想：slowIndex  : 已经删除val元素的新数组的下标的位置//fastIndex : 寻找新数组的元素 ，新数组就是不含有目标元素的数组for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {if (nums[fastIndex] != val) {//如果原数组中的元素不等于val，那么就是属于新数组的元素//复制到新数组中的对应的位置nums[slowIndex] = nums[fastIndex];slowIndex++;}}return slowIndex;}
}

977. 有序数组的平方

暴力解

class Solution {public int[] sortedSquares(int[] nums) {for (int i = 0; i < nums.length; i++) {nums[i] = nums[i] * nums[i];}Arrays.sort(nums);return nums;}
}

双指针

class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int[] res = new int[n];int left = 0, right = n - 1, index = n - 1;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {res[index--] = nums[left] * nums[left];++left;} else {res[index--] = nums[right] * nums[right];--right;}}return res;}
}

209. 长度最小的子数组

暴力解

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int res = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {sum=0;for (int j = i; j < nums.length; j++) {sum += nums[j];if (sum >= target) {res = (j - i + 1) < res ? (j - i + 1) : res;break;}}}return res == Integer.MAX_VALUE ? 0 : res;//如果res没有被赋值，说明数组元素的综合没有超过target}
}

滑动窗口：

class Solution {public int minSubArrayLen(int target, int[] nums) {int slow = 0,sum=0,res=Integer.MAX_VALUE;//slow 滑动窗口起始位置for(int fast = 0;fast<nums.length;fast++){sum+=nums[fast];while(sum>=target){// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件res=Math.min(res,fast-slow+1);sum-=nums[slow++];// 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）.可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。}}return res==Integer.MAX_VALUE?0:res;}
}

59. 螺旋矩阵 II

class Solution {public int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];int loop = 0, left = 0, right = n - 1, top = 0, bottom = n - 1, cnt = 1;while (loop <= n / 2) {for (int i = left; i <= right - 1; i++) {matrix[top][i] = cnt++;}for (int i = top; i <= bottom - 1; i++) {matrix[i][right] = cnt++;}for (int i = right; i >= left+1; i--) {matrix[bottom][i] = cnt++;}for (int i = bottom; i >= top+1; i--) {matrix[i][left] = cnt++;}loop++;left++;right--;bottom--;top++;}if(n%2!=0){matrix[n/2][n/2] = cnt;}return matrix;}
}

(2) 代码随想录：链表

203. 移除链表元素

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

输入：head = [], val = 1
输出：[]

输入：head = [7,7,7,7], val = 7
输出：[]

代码

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null)return null;//注意本题中的head节点并不是空节点，而是包含链表的首元素ListNode headTmp = new ListNode();//添加一个虚拟头结点，删除头结点就不用另做考虑headTmp.next = head;ListNode pre = headTmp;ListNode p = headTmp.next;while (p != null) {if (p.val == val) {pre.next = p.next;p = p.next;} else {pre = p;p = p.next;}}return headTmp.next;}
}

或者：删除头结点时另做考虑（由于头结点没有前一个结点）

https://leetcode.cn/problems/remove-linked-list-elements/solutions/10957/203yi-chu-lian-biao-yuan-su-by-lewis-dxstabdzew/

        while (head != null && head.val == val) {head = head.next;}

707. 设计链表

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3    （下标0 1 2）
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

代码：

注意：这里初始化添加的是虚拟头结点

class MyLinkedList {int size;ListNode head;public MyLinkedList() {size = 0;head = new ListNode(0);//注意这里初始化添加的是虚拟头结点}public int get(int index) {if (index < 0 || index >= size) {return -1;}ListNode cur = head;for (int i = 0; i <= index; i++) {cur = cur.next;}return cur.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if (index > size) {return;}index = Math.max(0, index);//当给出的index为负数，那就把它当为0ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}ListNode newNode = new ListNode(val);newNode.next = cur.next;cur.next = newNode;size++;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}cur.next = cur.next.next;size--;}
}class ListNode {int val;ListNode next;ListNode prev;public ListNode(int val) {this.val = val;}
}

206. 反转链表

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]

头插法逆置数组

建立一个新的虚拟头结点newHead，将原数组的每一个元素(从左到右)一个一个的摘下来，按照头插法插入到newHead后面，返回newHead.next

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode newHead = new ListNode();newHead.next=null;ListNode p=head;while(p!=null){ListNode tmp=p.next;p.next=newHead.next;newHead.next=p;p=tmp;}return newHead.next;}
}

双指针，不断修改指针的指向

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode cur=head;ListNode pre=null;while(cur!=null){ListNode tmp = cur.next; // 暂存后继节点 cur.nextcur.next=pre;pre=cur;cur=tmp;}return pre;}
}

24. 两两交换链表中的节点

输入：head = [1,2,3,4]
输出：[2,1,4,3]

输入：head = []
输出：[]

输入：head = [1]
输出：[1]

代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode Vhead = new ListNode(0);Vhead.next=head;ListNode in=Vhead;ListNode pre = in.next;ListNode p = pre.next;while(p != null) {pre.next = p.next;p.next = pre;in.next = p;in=pre;pre = in.next;if(pre==null){return Vhead.next;}p= pre.next;}return Vhead.next;}
}

19. 删除链表的倒数第 N 个结点

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

快慢指针

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(head.next==null)return null;ListNode dummyHead =new ListNode(0);dummyHead .next=head;ListNode slow=dummyHead ,fast=dummyHead  ;while(n!=0){fast=fast.next;n--;}while(fast.next!=null){slow=slow.next;fast=fast.next;}slow.next=slow.next.next;return dummyHead.next;}
}

面试题 02.07. 链表相交

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

快慢指针

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}int lengthA = 0, lengthB = 0;ListNode curA = headA, curB = headB;while (curA != null) {lengthA++;curA = curA.next;}while (curB != null) {lengthB++;curB = curB.next;}curA = headA;curB = headB;int len = Math.abs(lengthA - lengthB);while (lengthA > lengthB && len != 0) {curA = curA.next;len--;}while (lengthB > lengthA && len != 0) {curB = curB.next;len--;}while (curA != null || lengthA == lengthB) {if (curA == curB) {//一定一定注意这里是先判断 再移动return curA;}curA = curA.next;//移动curB = curB.next;}return null;}
}

(3) 代码随想录：哈希表

242. 有效的字母异位词

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length())return false;int[] record = new int[26];for (int i = 0; i < s.length(); i++) {record[s.charAt(i) - 'a']++;}for (int i = 0; i < t.length(); i++) {record[t.charAt(i) - 'a']--;}for (int count : record) {if (count != 0) { // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。return false;}}return true;}
}

349. 两个数组的交集

用数组来做哈希表

class Solution {public int[] intersection(int[] nums1, int[] nums2) {int []hash1 = new int[1001];int []hash2 = new int[1001];for (int i = 0; i < nums1.length; i++) {hash1[nums1[i]]++;}for (int i = 0; i < nums2.length; i++) {hash2[nums2[i]]++;}ArrayList<Integer> resTmp = new ArrayList<>();//ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。for (int i = 0; i < hash1.length; i++) {if (hash1[i] >0&&  hash2[i]>0) {//出现一次或者多次的，都记录其中了resTmp.add(i);}}int[] res = new int[resTmp.size()];for (int i = 0; i < res.length; i++) {res[i] = resTmp.get(i);}return res;}
}

Hashset

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();for (int num : nums1) {set1.add(num);}Set<Integer> set2 = new HashSet<>();for (int num : nums2) {if (set1.contains(num)) {set2.add(num);}}int[] result = new int[set2.size()];int index = 0;for (int num : set2) {result[index++] = num;}return result;}
}

202. 快乐数

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

输入：n = 2
输出：false

暴力解法

n转成str获取需要创建的数组的长度 n置0，

然后用str.charAt(i)-'0’来获取每一位的数字， 累加至n 循环；

判断无限循环的方法：设置loop如果loop过大就直接返回false。（仅适用于骗取测试点）

class Solution {public boolean isHappy(int n) {int loop=0;while(n!=1){String str = n+"";int length=str.length();
//        System.out.println(length);int []num=new int[length];n=0;for(int i=0;i<length;i++){num[i]=str.charAt(i)-'0';n+=num[i]*num[i];}loop++;if(loop==999){return false;}}return true;}
}

哈希

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要

(可能后面n会一直重复出现，或者几个数重复出现，不然不可能陷入无限的循环)

哈希主要为了判断是否陷入了无限循环

class Solution {public boolean isHappy(int n){Set<Integer> set = new HashSet<>();while(n!=1 && !set.contains(n)){set.add(n);n=getNextNum(n);//更新n}return n==1;//这个思想很重要}private int getNextNum(int n){int res=0;//需要注意的是，需要用到各个位数的时候，不需要将各个位存储到数组里面，直接拆然后更新n就行while(n!=0){int tmp=n%10;res += tmp*tmp;n=n/10;}return res;}
}

454. 四数相加 II

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

暴力

直接超时

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int count=0;for(int i=0;i<nums1.length;i++){for(int j=0;j<nums2.length;j++){for(int k=0;k<nums3.length;k++){for(int l=0;l<nums4.length;l++){if(nums1[i]+nums2[j]+nums3[k]+nums4[l]==0){count++;}}}}}return count;}
}

哈希

https://leetcode.cn/problems/4sum-ii/solutions/65894/chao-ji-rong-yi-li-jie-de-fang-fa-si-shu-xiang-jia/

Java HashMap getOrDefault() 方法：https://www.runoob.com/java/java-hashmap-getordefault.html

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map<Integer,Integer> map=new HashMap<>();for(int num1: nums1){for(int num2: nums2){int sum=num1+num2;map.put(sum,map.getOrDefault(sum,0)+1);//值为sum的数出现的次数，次数为 map.getOrDefault(sum,0)+1//map.getOrDefault(sum,0) 值为sum的数出现的次数，次数为键值对sum（key）对应的value//map.getOrDefault(sum,0) 作用是如果map里面没有key==sum的对，那么取默认值0；防止java丢出异常}}int res=0;for(int num3: nums3){for(int num4: nums4){res+=map.getOrDefault(-(num3+num4),0);}}return res;}
}

383. 赎金信

输入：ransomNote = "a", magazine = "b"
输出：false

输入：ransomNote = "aa", magazine = "ab"
输出：false

输入：ransomNote = "aa", magazine = "aab"
输出：true

数组哈希

一些同学可能想，用数组干啥，都用map完事了，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！

class Solution {public boolean canConstruct(String ransomNote, String magazine) {if(ransomNote.length() > magazine.length()) return false;int[] hash = new int[26];//默认初始全为0for (int i = 0; i < magazine.length(); i++) {hash[magazine.charAt(i) - 'a']++;}for (int i = 0; i < ransomNote.length(); i++) {hash[ransomNote.charAt(i) - 'a']--;if (hash[ransomNote.charAt(i) - 'a'] < 0) return false;}return true;}
}

15. 三数之和

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

双指针

https://leetcode.cn/problems/3sum/solutions/12307/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/

class Solution {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans = new ArrayList();int len = nums.length;if(nums == null || len < 3) return ans;Arrays.sort(nums); // 排序，nums变成递增数组for (int i = 0; i < len - 2 ; i++) {// i < nums.length - 2是为了保证后面还能存在两个数字if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环if(i > 0 && nums[i] == nums[i-1]) continue; // 去重  针对i指针（第一个数）  1112356int L = i+1;int R = len-1;while(L < R){int sum = nums[i] + nums[L] + nums[R];if(sum == 0){ans.add(Arrays.asList(nums[i],nums[L],nums[R]));while (L<R && nums[L] == nums[L+1]) L++; // 去重   针对L指针（第二个数）1222356  while (L<R && nums[R] == nums[R-1]) R--; // 去重   针对R指针（第三个数）1235666L++;R--;}else if (sum < 0) L++;else if (sum > 0) R--;}}        return ans;}
}

18. 四数之和

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

双指针

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();if (nums == null || nums.length < 4) {return res;}for (int i = 0; i < nums.length - 3; i++) {if (nums[i] > target && nums[i+1] >= 0) {break;} // 剪枝  如果第一个数已经大于target 而且后面的数不是负数，则终止if (i > 0 && nums[i] == nums[i - 1]) {continue;} // 去重for (int j = i + 1; j < nums.length - 2; j++) {if (nums[i] + nums[j] > target && nums[j+1] >= 0) {break;} // 剪枝  如果前两个数之和已经大于target 而且后面的数不是负数，则终止if (j > i + 1 && nums[j] == nums[j - 1]) {continue;} // 去重int L = j + 1;int R = nums.length - 1;while (L < R) { //******  注意这里不要忘记   *******  int sum = nums[i] + nums[j] + nums[L] + nums[R];if (sum == target) {res.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));while (L < R && nums[L] == nums[L + 1])L++;while (L < R && nums[R] == nums[R - 1])R--;L++;R--;} else if (sum < target)L++;else if (sum > target)R--;}}}return res;}
}

541. 反转字符串 II

输入：s = "abcdefg", k = 2
输出："bacdfeg"

输入：s = "abcd", k = 2
输出："bacd"

class Solution {public String reverseStr(String s, int k) {char[] chars = s.toCharArray();int len = chars.length;for (int i = 0; i < len; i += 2 * k) {//注意从开始就要判断i与len-1的关系，因为有可能字符串本身就很短，取不到i += 2 * kif (i + k - 1 > len - 1) {// 判断尾数够不够k个来决定end指针的位置reverse(chars, i, len - 1);return new String(chars);} else if (i + 2 * k - 1 > len - 1 && i + k - 1 >= len - 1) {// i+k-1<len-1<i+2k-1,判断len-1的范围 来决定end指针的位置reverse(chars, i, i + k - 1);return new String(chars);} else {reverse(chars, i, i + k - 1);}}return new String(chars);}private void reverse(char ch[], int start, int end) {for (int i = start, j = end; i < j; i++, j--) {char temp = ch[i];ch[i] = ch[j];ch[j] = temp;}}
}

class Solution {public String reverseStr(String s, int k) {char[] chars = s.toCharArray();int len = chars.length;for (int i = 0; i < len; i += 2 * k) {// 注意从开始就要判断i与len-1的关系，因为有可能字符串本身就很短，取不到i += 2 * kif (i + k - 1 > len - 1) {// 判断尾数够不够k个来决定end指针的位置reverse(chars, i, len - 1);return new String(chars);}reverse(chars, i, i + k - 1);}return new String(chars);}private void reverse(char ch[], int start, int end) {for (int i = start, j = end; i < j; i++, j--) {char temp = ch[i];ch[i] = ch[j];ch[j] = temp;}}
}

151. 反转字符串中的单词

输入：s = "the sky is blue"
输出："blue is sky the"

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。 

split分割

class Solution {public String reverseWords(String s) {String[] words = s.split(" ");String res = "";for (int i = words.length - 1; i >= 0; i--) {if (!words[i].equals(" ") && !words[i].equals("")) {res += words[i]+" ";}}return res.substring(0, res.length()-1);}
}

class Solution {public String reverseWords(String s) {String[] strs = s.trim().split(" ");        // 删除首尾空格，分割字符串StringBuilder res = new StringBuilder();for (int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表if (strs[i].equals("")) continue;        // 遇到空单词则跳过res.append(strs[i] + " ");              // 将单词拼接至 StringBuilder}return res.toString().trim();               // 转化为字符串，删除尾部空格，并返回}
}作者：Krahets
链接：https://leetcode.cn/problems/reverse-words-in-a-string/solutions/2361551/151-fan-zhuan-zi-fu-chuan-zhong-de-dan-c-yb1r/

不使用split

参考：https://leetcode.cn/problems/reverse-words-in-a-string/solutions/2810292/javapython3cshuang-zhi-zhen-mo-ni-ni-xu-lbdrk/

class Solution {public String reverseWords(String s) {StringBuilder res = new StringBuilder();    // 结果字符int i = 0;              // 用于表示首个非空字符的位置int j = s.length() - 1;   // 用于表示最后一个非空字符的位置while(i < j && s.charAt(i) == ' ')i++;     // 找到首个非空字符while(i < j && s.charAt(j) == ' ')j--;     // 找到最后一个非空字符for(;j >= i;){// 逆序反转单词[j+1, k]int k = j;      // 标记一个单词的结尾位置while(j >= i && s.charAt(j) != ' ')j--;    // 找到单词的起点res.append(s.substring(j + 1, k + 1));      // 截取单词加到结果上if(j >= i)res.append(' ');       // 如果非首个单词，之间用空格间隔while(j >= i && s.charAt(j) == ' ')j--;    // 找到下一个单词的结尾位置}return res.toString(); }
}

28. 找出字符串中第一个匹配项的下标（KMP）

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

年轻人不讲武德：return haystack.indexOf(needle); 结束睡觉保养头发

return haystack.indexOf(needle);

459. 重复的子字符串

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

输入: s = "aba"
输出: false

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

class Solution {public boolean repeatedSubstringPattern(String s) {String str = s + s;return str.substring(1, str.length() - 1).contains(s);
}
}作者：Goodlucky
链接：https://leetcode.cn/problems/repeated-substring-pattern/solutions/114572/jian-dan-ming-liao-guan-yu-javaliang-xing-dai-ma-s/
来源：力扣（LeetCode）

其他

1.滑动窗口

https://leetcode.cn/discuss/post/3578981/ti-dan-hua-dong-chuang-kou-ding-chang-bu-rzz7/

567. 字符串的排列

class Solution {public boolean checkInclusion(String s1, String s2) {char []ch1=s1.toCharArray();int len=ch1.length;Arrays.sort(ch1);for(int l=0,r=len;r<=s2.length();l++,r++){String tmp=s2.substring(l,r);char []tmpch=tmp.toCharArray();Arrays.sort(tmpch);if(Arrays.equals(ch1,tmpch)){return true;}}return false;}
}

class Solution {public boolean checkInclusion(String s1, String s2) {int n = s1.length(), m = s2.length();if (n > m) {return false;}int[] cnt1 = new int[26];int[] cnt2 = new int[26];for (int i = 0; i < n; ++i) {++cnt1[s1.charAt(i) - 'a'];++cnt2[s2.charAt(i) - 'a'];}if (Arrays.equals(cnt1, cnt2)) {return true;}for (int i = n; i < m; ++i) {++cnt2[s2.charAt(i) - 'a'];--cnt2[s2.charAt(i - n) - 'a'];if (Arrays.equals(cnt1, cnt2)) {return true;}}return false;}
}

3. 无重复字符的最长子串

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

class Solution {public int lengthOfLongestSubstring(String s) {Map<Character,Integer> map=new HashMap<>();int res=0;for(int l=0,r=0;r<s.length();r++){char c=s.charAt(r);// 使用 merge 方法更新字符 c 在 map 中的出现次数// 如果 c 已经在 map 中，将其计数加 1；如果不在，将其计数初始化为 1map.merge(c,1,Integer::sum);// 当字符 c 在当前窗口中的出现次数大于 1 时，说明出现了重复字符// 需要移动左指针 l 来缩小窗口，直到没有重复字符while(map.get(c)>1){char lc=s.charAt(l);map.merge(lc,-1,Integer::sum);l++;// 左指针右移一位，缩小窗口}res= Math.max(res,r-l+1);}return res;}
}

3090. 每个字符最多出现两次的最长子字符串

class Solution {public int maximumLengthSubstring(String s) {Map<Character,Integer> map=new HashMap<>();int res=0;for(int l=0,r=0;r<s.length();r++){//  [l,r)   保证起始的时候l=0 r=0没有元素char c=s.charAt(r);map.merge(c,1,Integer::sum);while(map.get(c)>2){map.merge(s.charAt(l),-1,Integer::sum);l++;}res=Math.max(res,r-l+1);//区间是左闭右开的 长度按理来说应该是r-L  但是此时r还没有++}return res;}
}

1493. 删掉一个元素以后全为 1 的最长子数组

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

class Solution {public int longestSubarray(int[] nums) {int maxLength = 0;Map<Integer, Integer> map = new HashMap<>();for (int left = 0, right = 0; right < nums.length; right++) {if (nums[right] == 0) {map.merge(0, 1, Integer::sum);}// 当 0 的数量超过 1 个时，需要缩小窗口while (map.getOrDefault(0, 0) > 1) {if (nums[left] == 0) {map.merge(0, -1, Integer::sum);}left++;}// 更新最长子数组的长度maxLength = Math.max(maxLength, right - left);}return maxLength;}
}

### [1493. 删掉一个元素以后全为 1 的最长子数组](https://leetcode.cn/problems/longest-subarray-of-1s-after-deleting-one-element/)给你一个二进制数组 `nums` ，你需要从中删掉一个元素。请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组，请返回 0 。**提示 1：**

**示例 2：**

```java
class Solution {public int longestSubarray(int[] nums) {int maxLength = 0;Map<Integer, Integer> map = new HashMap<>();for (int left = 0, right = 0; right < nums.length; right++) {if (nums[right] == 0) {map.merge(0, 1, Integer::sum);}// 当 0 的数量超过 1 个时，需要缩小窗口while (map.getOrDefault(0, 0) > 1) {if (nums[left] == 0) {map.merge(0, -1, Integer::sum);}left++;}// 更新最长子数组的长度maxLength = Math.max(maxLength, right - left);}return maxLength;}
}