Mako Shan

Mako 是一名密码朋克爱好者
这里是我记录生活和成长的地方

联系我的微信号
👏欢迎一起交流学习

1. Two Sum

https://leetcode.com/problems/two-sum


Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

point : 排序,二分查找

如何高效检查一个数组中是否包含某个值。 Arrays.sort 排序,然后用Arrays.binarySearch的方法

public class Solution1 {
     public static int[] twoSum(int[] numbers, int target)   {
            int[] num = numbers.clone();
            Arrays.sort(num);
            int size = num.length;
            int[] answers = new int[2];
            for(int i=0;i<size;i++)  {
                if(Arrays.binarySearch(num, target-num[i])>0)     {
                        int count=0,index1 = 0,index2=0;
                        for(int j=0;j<size;j++)  {
                            if(numbers[j]==num[i]||numbers[j]==target-num[i])  {
                                count++;
                                if(count==2)  {
                                    index2=j;
                                    answers[0] = (index1<index2?index1:index2)+1;
                                    answers[1] = (index1>index2?index1:index2)+1;
                                    break;
                                }
                                else   {
                                    index1=j;
                                }
                            }
                        }                   
                }
            }
            return answers;
        }
}
public class Solution2 {
  public  int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int difference = target - nums[i];
            if (map.containsKey(difference) && (map.get(difference)!=i)) {
                result[1] = map.get(difference)+1;
                result[0] = i + 1;
                break;
            }
        }
        return result;
    }
}
public class Solution3 {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < numbers.length; i++) {
            if (map.get(numbers[i]) != null) {
                int[] result = {map.get(numbers[i]), i            };
                return result;
            }
            map.put(target - numbers[i], i);
        }
        
        int[] result = {};
        return result;
    }
}
0
私人电台
目录