---

前言

1、等差子数组
2、寻找重复数
3、缺失的第一个正数
4、等差子数组

---

一、环形链表||（力扣142）

分析：
快慢指针 快指针一直一次走两步 慢指针一次走一步
先判断是否有环 快慢指针是否会相等
在有环的基础上，去找入口位置

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){//先判断是否有环slow = slow.next;fast = fast.next.next;if(slow==fast){//有环ListNode index1 = fast;ListNode index2 = head;//找入口 while(index1!=index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}

二、寻找重复数（力扣287）

分析：将其转化为环形链表||
大佬题解

class Solution {public int findDuplicate(int[] nums) {int res = 0;int slow = 0;int fast = 0;slow = nums[slow];fast = nums[nums[fast]];//由题意得一定会出现环while(slow!=fast){slow = nums[slow];fast = nums[nums[fast]];}//此时slow和fast相遇//寻找相遇的入口int index1 = 0;int index2 = slow;while(index1!=index2){index1 = nums[index1];index2 = nums[index2];}res = index1;return res;}
}

三、缺失的第一个正数（力扣41）

分析：

如果没有额外的时空复杂度要求，那么就很容易实现：
将数组所有的数放入哈希表，随后从 1开始依次枚举正整数，并判断其是否在哈希表中；
我们可以从 1 开始依次枚举正整数，并遍历数组，判断其是否在数组中。
如果数组的长度为 N，那么第一种做法的时间复杂度为 O(N)，空间复杂度为 O(N)；第二种做法的时间复杂度为 O(N2)，空间复杂度为 O(1)。但它们都不满足时间复杂度为 O(N) 且空间复杂度为 O(1)。

力扣题解

==注意：==特别需要注意第二步：

    for(int i=0;i<nums.length;i++){if(nums[i]<=n && nums[i]>0){nums[nums[i]-1] = -1*nums[nums[i]-1];}}

这样写的问题所在在于： 例如 3,4,-1,1
经过第一步后变为：3，4，5，1；
按上述代码执行第二步后：3，4，-5，-1；
问题在于变为-1后 3无法标记为-3， 因此要用取绝对值的方式

    for(int i=0;i<nums.length;i++){int num = Math.abs(nums[i]);if(num<=n){nums[num-1] = -Math.abs(nums[num-1]);}}

class Solution {
public int firstMissingPositive(int[] nums) {int n = nums.length;for(int i=0;i<nums.length;i++){if(nums[i]<=0){nums[i] = n+1;}}for(int i=0;i<nums.length;i++){int num = Math.abs(nums[i]);if(num<=n){nums[num-1] = -Math.abs(nums[num-1]);}}for(int i=0;i<n;i++){if(nums[i]>0){return i+1;}}return n+1;}
}

---

每日一题day73：等差子数组（力扣1630）

分析：
简单模拟 数据量不大 暴力求解不会超时
截取每一段数组 排序 依次判断差值是否相等

class Solution {public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {//int length = l.length;Boolean[] res = new Boolean[length];Arrays.fill(res,true);for(int i=0;i<length;i++){int left = l[i];int right = r[i];int[] curArray = Arrays.copyOfRange(nums,left,right+1);Arrays.sort(curArray);int gap = curArray[1]-curArray[0];for(int j=2;j<curArray.length;j++){int diff = curArray[j]-curArray[j-1];if(diff!=gap){res[i] = false;break;}}}return Arrays.asList(res);}
}