网站开发学些什么,北京王府井简介,展示型的网站开发价格,嘉兴秀宏建设公司网站解题思路
Step1#xff1a;先对数组排序#xff0c;然后设置3个指针#xff0c;指针1遍历范围为#xff08;0~数组长度减2#xff09;。
Step2#xff1a;指针1位置确定时#xff0c;指针1后面的数组元素首位各放置一个指针#xff08;指针2、指针3#xff09;。
S… 解题思路
Step1先对数组排序然后设置3个指针指针1遍历范围为0~数组长度减2。
Step2指针1位置确定时指针1后面的数组元素首位各放置一个指针指针2、指针3。
Step3如果三数之和target则返回target值如果三数之和target则将指针2往后移动如果三数之和target则将指针3往前移动。
Step4当指针2和指针3重合时则将指针1往后移动。
Step5重复 Step2 到 Step4。直到指针1遍历完。
Java代码
import java.util.Arrays;public class ThreeSumClosest {public static void main(String[] args) {Solution sol new Solution();System.out.println(sol.threeSumClosest(new int[]{-1, 2, 1, -4}, 1));}
}class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int n nums.length;int min_diff Integer.MAX_VALUE;//当前找到的三数之和与target的最小差值int ans 0;//最小差值对应的三数之和int cur_sum 0;int cur_diff 0;for (int i 0; i n - 2; i) {//优化一如果有重复元素则跳过if (i 0 nums[i] nums[i - 1]) {continue;}//优化二如果加上最后面两个数依旧没有target大则判断一下三数之和之后跳过当前循环cur_sum nums[i] nums[n - 2] nums[n - 1];if (target cur_sum) {cur_diff target - cur_sum;if (cur_diff 0) {return target;}if (cur_diff min_diff) {ans cur_sum;min_diff cur_diff;}continue;}//优化三前面3个数的和已经target则判断三数之和之后跳出循环cur_sum nums[i] nums[i 1] nums[i 2];if (target cur_sum) {cur_diff cur_sum - target;if (cur_diff 0) {return target;}if (cur_diff min_diff) {ans cur_sum;}break;}int j i 1, k n - 1;while(j k){cur_sum nums[i] nums[j] nums[k];if (cur_sum target) {return target;}cur_diff target - cur_sum;if (cur_sum target) {if (cur_diff min_diff) {ans cur_sum;min_diff cur_diff;}j;} else { //cur_sum targetcur_diff -cur_diff;if (cur_diff min_diff) {ans cur_sum;min_diff cur_diff;}k--;}}}return ans;}
}
Python代码
class Solution(object):def threeSumClosest(self, nums, target):nums sorted(nums) # or nums.sort()n len(nums)min_diff float(inf)ans 0for i in range(n-2):# 优化一如果有重复元素则跳过if i 0 and nums[i] nums[i-1]:continue# 优化二如果加上最后面两个数依旧没有target大则判断一下三数之和之后跳过当前循环cur_sum nums[i] nums[n - 2] nums[n - 1]if target cur_sum:cur_diff target - cur_sumif cur_diff 0:return targetif cur_diff min_diff:ans cur_summin_diff cur_diffcontinue# 优化三前面3个数的和已经target则判断三数之和之后跳出循环cur_sum nums[i] nums[i 1] nums[i 2]if target cur_sum:cur_diff cur_sum - targetif cur_diff 0:return targetif cur_diff min_diff:ans cur_sumbreakj, k i 1, n - 1while j k:cur_sum nums[i] nums[j] nums[k]if cur_sum target:return targetcur_diff target - cur_sumif cur_sum target:if cur_diff min_diff:ans cur_summin_diff cur_diffj 1else:cur_diff -cur_diffif cur_diff min_diff:ans cur_summin_diff cur_diffk - 1return ansif __name__ __main__:sol Solution()print(sol.threeSumClosest([-1, 2, 1, -4], 1)) # 2
完整题目
16. 最接近的三数之和
给你一个长度为 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提示
3 nums.length 1000-1000 nums[i] 1000-10^4 target 10^4
