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;
}