近期正在学习go语言，闲暇时间写点leetcode，正好当作熟悉语法，锻炼思路。有些类似的题目，也做些总结和思考。很久以前就特别佩服那些写技术博客的，一直都是懒性子，总算是让自己迈开了第一步，第一篇技术博客，算法、工程、生活，希望自己能多总结，加油！
题目一：一个数组，找到两个数的和等于某一个值
1、题目链接
leetcode No1：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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
题目的意思是，一个数组，找到其中两个数，和为某个给定的值。
2、Solution
方法一：暴力解法
直接两层for循环，时间复杂度是O(n^2),空间复杂度是O(1)。
方法二：借助一个hashmap遍历两遍
func twoSum(nums []int, target int) []int {
var sumMap = make(map[int]int)
var res = make([]int,2)
for i,v := range nums {
sumMap[target-v] = i
}
for i,v:=range nums{
if i2,ok:=sumMap[v];ok{
if i!=i2 {
res[0] = i
res[1] = i2
return res
}
}
}
return res
}
时间复杂度是O(n),空间复杂度是O(n)
方法三：借助一个hashmap，遍历一次
func twoSum(nums []int, target int) []int {
var sumMap = make(map[int]int)
for i,v := range nums {
if i2,ok:=sumMap[v];ok{
return []int{i2,i}
}
sumMap[target-v] = i
}
return []int{}
}
顺道附上java版本的解法：
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
res[0]=map.get(nums[i]);
res[1]=i;
break;
}
map.put(target-nums[i],i);
}
return res;
}
}
题目二：一个有序的数组，找到两个数的和等于某一个值
1、题目链接
leetcode No167:https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
这个题也完成可以按照上面leetcodeNo1的hashmap的解法，这种实际上并没有利用上这个是有序数组的优势。
2、Solution：双指针思路
go版本实现：
func twoSum(numbers []int, target int) []int {
var i int = 0
var j int = len(numbers)-1
for i<j {
var curSum = numbers[i] + numbers[j]
if curSum == target {
return []int{i+1,j+1}
}else if curSum < target{
i++
}else{
j--
}
}
return []int{}
}
java版本的实现：
public int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length-1;
int[] res = new int[2];
while(i<j){
int cur = numbers[i] + numbers[j];
if(cur==target){
res[0]=i+1;
res[1]=j+1;
return res;
}else if(cur>target)
j--;
else
i++;
}
return res;
}
题目三：二叉排序树，找到两个数的和等于某一个值
1、题目链接
leetcode No653:https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
Output: False
2、Solution
方法一:遍历一遍BST，将树转化成一个有序的数组，再用双指针思路，变成上述题目二。
空间复杂度O(n)，时间复杂度O(n)
方法二:遍历二叉树+hashmap存储
func findTarget(root *TreeNode, k int) bool {
var sumMap = make(map[int]bool)
return dfs(root,k,sumMap)
}
func dfs(root *TreeNode, k int, sumMap map[int]bool) bool{
if root == nil {
return false
}
if _,ok := sumMap[root.Val];ok {
return true
}
sumMap[k-root.Val] = true
return dfs(root.Left,k,sumMap) || dfs(root.Right,k,sumMap)
}
