Leetcode 16.convert sorted list to binary search tree

26 Jun 2018

Reading time ~1 minute

Leetcode 16.Convert Sorted List to Binary Search Tree

题目：

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

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

主要思路是双指针，从第一个到倒数第三个元素循环，循环中再用两个指针指向i+1和最后这两个元素，将i， i+1,end这三个索引的数相加，若和大于目标值，右指针左移，反之左指针右移，直至两指针相遇。若和更接近目标值则更新答案。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int last = nums[0] + nums[1] + nums[2];
        int temp;
        Arrays.sort(nums);
        int start, end;
        for (int i = 0; i < nums.length - 2; i++) {
            start = i + 1;
            end = nums.length - 1;
            while (start < end) {
                if (Math.abs(nums[i] + nums[start] + nums[end] - target) < 
                        Math.abs(last - target)) {
                    last = nums[i] + nums[start] + nums[end];
                }
                if ((nums[i] + nums[start] + nums[end]) > target) {
                    end--;
                } else {
                    start++;
                }
            }
        }
        return last;
    }
}