最小差值
给你一个整数数组 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;
}