首页 > 代码库 > Two Sum
Two Sum
leetcode
给定一个整数数组和一个指定的目标值,在数组中找到两个数加起来等于指定的目标值,返回这两个值的下标。
可以假设每个数组只有一个唯一的答案,切数组中没有重复的值:
例子:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
1:双循环找出答案
1 public int[] twoSum(int[] nums, int target) { 2 int len; 3 if (nums == null || (len = nums.length) == 0) { 4 return null; 5 } 6 int[] ret = new int[2]; 7 8 boolean flag = false; 9 for (int i = 0; i < len - 1; i++) { 10 int a = nums[i]; 11 for (int j = i+1; j < len; j++) { 12 int b = nums[j]; 13 if (a + b == target) { 14 ret[0] = i; 15 ret[1] = j; 16 flag = true; 17 break; 18 } 19 } 20 if (flag) { 21 break; 22 } 23 } 24 return ret; 25 }
2,借助map,一次循环
1 public int[] twoSum(int[] nums, int target) { 2 int len; 3 if (nums == null || (len = nums.length) == 0) { 4 return null; 5 } 6 int[] ret = new int[2]; 7 int tekk = nums.length * 4 / 3; 8 Map<Integer, Integer> map = new HashMap<Integer, Integer>(tekk); 9 for (int i = 0; i < len; i++) { 10 int temp = target - nums[i]; 11 if (map.containsKey(temp)) { 12 ret[0] = map.get(temp); 13 ret[1] = i; 14 break; 15 } else { 16 map.put(nums[i], i); 17 } 18 } 19 return ret; 20 }
在使用HashMap时,不指定大小,初始大小是16,如果数值大于16会rehash,既然知道数组的大小,可以新建HashMap时直接给定初始大小
3,如果数组是有序的,可以一次循环找出答案
1 public int[] twoSum(int[] nums, int target) { 2 int len; 3 if (nums == null || (len = nums.length) == 0) { 4 return null; 5 } 6 int[] ret = {0, len-1}; 7 Arrays.sort(nums); 8 while (ret[0] < ret[1]) { 9 int a = nums[ret[0]]; 10 int b = nums[ret[1]]; 11 if (a + b == target) { 12 break; 13 } else if (a + b < target) { 14 ret[0]++; 15 } else if (a + b > target) { 16 ret[1]--; 17 } 18 } 19 return ret; 20 }
Two Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。