阅读 27

LeetCode最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/3s…

解题思路

  1. 先将数组排序
  2. 给个初始值
  3. 左指针
  4. 右指针
  5. 循环判断
  6. 获取三数之和之后,比较当前总和和初始值比较。将当前值赋值给init
  7. 比较当前值和目标值的大小,大于,右指针向左移动
  8. 小于,左指针向右移动
  9. 等于直接返回
public int threeSumClosest(int[] nums, int target) {
        // 1
        Arrays.sort(nums);
        // 2
	int init = nums[0] + nums[1] + nums[2];
	for (int i = 0; i <nums.length; i++) {
		// 3
		int left = i + 1;
		// 4
		int rigth = nums.length - 1;
		// 5
		while (left < rigth) {
			int sum = nums[i] + nums[left] + nums[rigth];
			// 6
			if (Math.abs(target - sum) < Math.abs(target - init)) {
				init = sum;
			}
			// 7
			if (sum > target) {
				rigth--;
			// 8
			} else if (sum <target) {
				left++;
			// 9
			} else {
				return init;
			}
		}
	}
	return init;
    }
复制代码
关注下面的标签,发现更多相似文章
评论