来自 澳门金莎娱乐手机版 2019-11-14 16:49 的文章
当前位置: 金沙澳门官网网址 > 澳门金莎娱乐手机版 > 正文

【澳门金莎娱乐手机版】【LeetCode OJ 016】3Sum Cl

【LeetCode OJ 016】3Sum Closest

题目:Given an arraySofnintegers, find three integers inSsuch that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

 For example, given array S = {-1 2 1 -4}, and target = 1.

 The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解题思路:先对数组举办排序,然后遍历数组,寻找和最雷同target的数。示例代码:

import java.util.Arrays;
public class Solution
{
    public int threeSumClosest(int[] nums, int target)
    {
     int length=nums.length;
     int minNum=Integer.MAX_VALUE;
     int tempsubNum=Integer.MAX_VALUE; 
     Arrays.sort(nums);//先对nums进行排序
     for(int i=0;i

OJ 016】3Sum Closest 题目:Given an arraySofnintegers, find three integers inSsuch that the sum is closest to a given number, target. Return the sum of the three in...

LeetCode -- 3Sum Closest

难题汇报:
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

主题与 Three Sum Zero形似,分歧点在于,在此之前是研究a+b+c=0的组成,现在是找最周围target的a+b+c的值。

思路:
依然是two pointer的思路。
1.对数组排序
2.使用a表示最近第i轮查找,b=i+1,表示第i轮的首个要素,b∈[i+1,n),c=len-1,意气风发开头针对最终两个要素。
3.当找到a+b+c=target,直接回到;假使a+b+c < target,b++;不然,c--。
4.老是取Math.Abs(a+b+c- target)与眼下Math.Abs(min-target)的矮小值。
5.最终回来min

落到实处代码:

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) 
    {
        if(nums == null || nums.Length < 3){
      return nums.Sum();
     }

     var list = nums.OrderBy(x=>x).ToList();

     var len = list.Count;

     int? min = null;

     for (var i = 0 ;i <= len - 3 ;i++)
     {
      var a = list[i];
      var start = i+1;
      var end = len-1;
      while (start < end) 
      {
       var b = list[start];
       var c = list[end];
       if(a+b+c == target){
        min = target;
        break;
       }
       else if (a+b+c > target){
        end --;
       }
       else{
        start ++;
       }
       // update min
       if (min == null || Math.Abs(a+b+c - target) < Math.Abs(min.Value - target)) 
       {
        min = a+b+c;
       }
      }
     }

     return min.Value;
    }
}

-- 3Sum Closest 主题材料叙述: Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the thre...

本文由金沙澳门官网网址发布于澳门金莎娱乐手机版,转载请注明出处:【澳门金莎娱乐手机版】【LeetCode OJ 016】3Sum Cl

关键词: