leetcode day1
最小差值
给你一个整数数组 nums，和一个整数 k 。
在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。
nums 的 分数 是 nums 中最大和最小元素的差值。
在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。
示例 1：
输入：nums = [1], k = 0
输出：0
解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。
示例 2：
输入：nums = [0,10], k = 2
输出：6
解释：将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。
示例 3：
输入：nums = [1,3,6], k = 3
输出：0
解释：将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。
提示：
1 <= nums.length <= 104
0 <= nums[i] <= 104
0 <= k <= 104
解题思路：先对数组排序
1、考虑数组可变为相等数的情况，x为数组任意元素，x-min<=k,max-x<=k,这种情况满足
即max-min<=2*k，此时最低 分数=0
2、max-min>2*k时，最低分数=max-k-(min+k)=max-min-2*k
当x<min+k时，x可以加一个比k小的数达到min+k
当x>max-k时，x可以减一个比k小的数达到max-k
int cmp(const void *a,const void *b){
return *(int*)a-*(int*)b;
}
int smallestRangeI(int* nums, int numsSize, int k) {
qsort(nums,numsSize,sizeof(int),cmp);
if(nums[numsSize-1]-nums[0]<=2*k)return 0;
else return nums[numsSize-1]-nums[0]-2*k;
}
最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
解题思路：利用三层循环会超时
先枚举第一个元素，从[i+1,numsSize)的范围枚举j,k对应数
如果 a+b+c≥target，那么就将 c指针左移一位；注意考虑指针的范围j<k
如果 a+b+c<target，那么就将 b指针右移一位。
int cmp(const void *a,const void *b){
return *(int *)a-*(int *)b;
}
int threeSumClosest(int* nums, int numsSize, int target) {
qsort(nums,numsSize,sizeof(int),cmp);
int sum,close=1e7;
for(int i=0;i<numsSize;i++){
int j=i+1,k=numsSize-1;
if(i>0&&nums[i]==nums[i-1])continue;
while(j<k){
sum=nums[i]+nums[j]+nums[k];
if(sum==target)return target;
if(abs(sum-target)<abs(close-target))close=sum;
if(sum>target){
int k0=k-1;
while(j<k0&&nums[k0]==nums[k])k0--;
k=k0;
}
else{
int j0=j+1;
while(j0<k&&nums[j0]==nums[j])j0++;
j=j0;
}
}
}
return close;
}