本文主要是介绍leetcode 题解 1. Two Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解法一
leetcode的第一题，不是非常困难，使用暴力方法就可以解决，相似问题就不能这么做了。直接将答案分享出来。
时间复杂度：O(n^2)
空间复杂度：O(1)
C代码
int* twoSum(int* nums, int numsSize, int target) {int i,j;int* result = (int*)malloc(2*sizeof(int));for(i=0;i<numsSize;i++){for(j=i+1;j<numsSize;j++){if(nums[i]+nums[j]==target){result[0] = i;result[1] = j;break;}}}return result;
}
Java代码
class Solution {public int[] twoSum(int[] nums, int target) {int[] result = new int[2];for(int i=0;i<nums.length;i++){for(int j=i+1;j<nums.length;j++){if(target==nums[i]+nums[j]){result[0] = i;result[1] = j;}}}return result;}
}
解法二
既然已经知道了其中一个数与结果，问题也就转化为在序列中查找另一个数，此处也就有了两种做法，第一种可以利用二分查找方法，这是《挑战程序设计竞赛》一书中给出的做法；另一种做法是leetcode官网中给出的做法，利用库函数进行查找，而查找效率最高的方法莫过于hash，因此直接利用hash。
利用二分搜索的时间复杂度：O(nlog2n)，空间复杂度：O(1)。
利用hash的时间复杂度：O(n)，空间复杂度：O(n)。
给出利用hash的java代码：
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){map.put(nums[i],i);}for(int i=0;i<nums.length;i++){int search_num = target - nums[i];if(map.containsKey(search_num)&&map.get(search_num)!=i){return new int[]{i,map.get(search_num)};}}throw new IllegalArgumentException("No two sum solution");}
}
解法三：
解法二中是对序列遍历两次，解法三则是一边遍历，一边查找是否存在结果，若存在则直接返回。
Java代码如下：
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){int search_num = target - nums[i];if(map.containsKey(search_num)){return new int[]{map.get(search_num),i};}map.put(nums[i],i);}throw new IllegalArgumentException("No two sum solution");}
}
这篇关于leetcode 题解 1. Two Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
