Leetcode Array 442,15 @Java－CONY的世界

442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Success:

想法可以回去看之前的python 版本 http://angledark0123.pixnet.net/blog/post/65753368

想法是一樣的，follow 題目特殊的設定，把沒遇過的值反向，只要之後再遇到就會因為已經是負的得知以重複

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        for(int element:nums) {
            if (nums[Math.abs(element)-1] < 0)
                result.add(Math.abs(element));
            else
                nums[Math.abs(element)-1] = -nums[Math.abs(element)-1];
        }
        return result;
    }
}

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Success: 官方解法

50.68% Runtime: 85 ms

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int index=0; index < nums.length-2; index++) {
            if((index > 0) && (nums[index] == nums[index-1]))
                continue;
            int target = -nums[index];
            int i = index+1, k = nums.length-1 ;
            while (i < k) {
                if(nums[i] + nums[k] == target) {
                    res.add(Arrays.asList(nums[index], nums[i], nums[k]));
                    i++;
                    k--;
                    while ((i < k) &&(nums[i] == nums[i-1]))
                        i++;
                    while ((i < k) &&(nums[k] == nums[k+1]))
                        k--;
                } else if (nums[i] + nums[k] > target)
                    k--;
                else if (nums[i] + nums[k] < target)
                    i++;
            }
        }
        return res;
    }
}

16. 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).

錯誤寫法.....不要再用O(n^3) 的方式寫了！！！雖然很直觀，但是太慢了！

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Set<int> Set = HashSet()
        int res = nums[0]+nums[1]+nums[2];
        for(int i=0; i<nums.length-2; i++) {
            for(int j=i+1; j<nums.length-1; j++) {
                for(int k=j+1; k< nums.length; k++){
                    int sum = nums[i]+nums[j]+nums[k];
                    if(Math.abs(target-res) > Math.abs(target-sum)) {
                        res = sum;
                    }
              }
            }
        }
        return res;
    }
}