近期正在学习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) 
}