我这里第二个好像是7.2号的题，看错题了。
最后一题有点难度，我不太会，就不往笔记里面写了。
高校算法学习社区
第一题：
- 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
int l=0,r= nums.length-1;
while (r>=l){
int mid=(l+r)/2;
if (target==nums[mid]){
return mid;
}else if (target>nums[mid]){
l=mid+1;
}else {
r=mid-1;
}
}
return -1;
}
}
思路：
二分查找
在升序数组nums 中寻找目标值 target，对于特定下标 i，比较 nums[i] 和 target 的大小：
如果 nums[i]=target，则下标 i 即为要寻找的下标；
如果nums[i]>target，则 target 只可能在下标 i 的左侧；
如果 [i] < nums[i]<target，则target 只可能在下标 i 的右侧。
基于上述事实，可以在有序数组中使用二分查找寻找目标值。
二分查找的做法是，定义查找的范围 [left,right]，初始查找范围是整个数组。每次取查找范围的中点 mid，比较 [mid] 和target 的大小，如果相等则mid 即为要寻找的下标，如果不相等则根据 [mid] 和 target 的大小关系将查找范围缩小一半。
由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 O(\log n)O(logn)，其中 nn 是数组的长度。
二分查找的条件是查找范围不为空，即 left≤right。如果target 在数组中，二分查找可以保证找到 target，返回target 在数组中的下标。如果 target 不在数组中，则当 left>right 时结束查找，返回 ?1。
这是力扣的官方题解，我下面题解都尽量用官方的，以免哪里出错误导你们了，毕竟我对算法这里也是小白，哈哈哈。
力扣官方题解
第二题
- 给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target
目标下标 是一个满足 nums[i] == target 的下标 i 。
将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-target-indices-after-sorting-array
public class Solution {
public List<Integer> targetIndices(int[] nums, int target) {
List<Integer> res = new ArrayList<>();
Arrays.sort(nums);//对数组进行排序
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
res.add(i);
}
}
return res;
}
}
这是我自己的提交界面。
方法一：排序后遍历
思路与算法
我们首先按要求对 nums 数组升序排序，随后从左到右遍历数组中的所有元素，并按顺序记录所有数值等于 target 的元素的下标。这样我们可以保证记录的下标数组中的下标（如果存在）必定按照递增顺序排列。
最后，如果符合要求的下标存在，我们返回记录的下标数组作为答案；如果不存在，我们返回空数组即可。
复杂度分析
- **时间复杂度：**O(n \log n)O(nlogn)，其中 nn 为 \textit{nums}nums 的长度。排序的时间复杂度为 $O(n \log n)，遍历记录目标下标数组的时间复杂度为 O(n)O(n)。
- **空间复杂度：**O(\log n)O(logn)，即为排序的栈空间开销。
- 方法二：直接统计数量
思路与算法
我们也可以不对数组排序来构造目标下标。
在排序后数组中，这些数值等于 target 的元素的下标（如果存在）一定是连续的。因此，我们可以通过寻找目标下标的左边界（即最小值，如果存在，下同）和目标下标的数量来构造目标下标数组。
由于数组是升序排序的，数值等于target 的元素一定在数值小于target 的元素的右侧，因此目标下标的左边界即为数组中数值小于 target 的元素数量。而目标下标的数量即为数组中数值等于 target 的元素数量。
我们遍历未排序的数组，计算数值小于target 的元素数量 cnt1与数值等于 target 的元素数量 cnt2，则此时目标下标即为 [cnt1,cnt1 +cnt 2) 左闭右开区间内的所有整数。我们按照递增的顺序构造对应的下标数组（可能为空）并返回即可。
力扣官方题解
官方的题解是只有C++，Python版的，可以参考一下，我个人做这题时是先新建一个链表 res，用于存储nums数组中的目标下标，利用for循环嵌套if条件句来实现目标下标的存储，如果没有，返回res即可。
易错点：
1.新建的是链表而不是数组，一定要审清楚题
2.最后返回的时候如果没有目标下标，直接返回res即可。
我当时就是脑子蒙了，居然去return null；别跟我一样啊。
第三题
给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。
返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。
- 1 <= nums.length <= 10的5次方
- 0 <= nums[i] <= 10的5次方
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-increment-to-make-array-unique
这是我的代码
public class Solution5 {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums);
//操作次数
int fre = 0;
//遍历数组，若当前元素小于等于它的前一个元素，则将其变为前一个数+1
for (int i = 1; i < nums.length; i++) {
int cur=nums[i];
if(cur<=nums[i-1]){
fre+=nums[i-1]-cur+1;
nums[i] = nums[i-1]+1;
}
}
return fre;
}
}
我这里是先对数组进行排序，然后遍历，如果数组的当前值小于等于前一个值，就让当前值 等于前一个值加一，记录操作次数，最后返回。
力扣官方题解
https://leetcode.cn/problems/minimum-increment-to-make-array-unique/solution/shi-shu-zu-wei-yi-de-zui-xiao-zeng-liang-by-leet-2/
第四题
- 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-duplicate-number
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre1 = 0;
int pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}