【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST

1. 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 exactlyone 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].

 1 int* twosum(int* nums, int numssize, int target) {
 2     int *svalue = (int *)malloc(2 * sizeof(int));
 3     for(int i = 1; i < numssize; i++)
 4     {
 5         for(int j = 0; j < i; j++)
 6         {
 7             if(nums[i] + nums[j] == target)
 8             {
 9                 svalue[0] = i;
10                 svalue[1] = j;
11                 return svalue;
12             }
13         }
14     }
15     return null;
16 }

 解题思路：

嵌套两层循环：

　　第一层：1 <= i <= numssize

　　第二层： 0 <= j < (i - 1)因为i的取值是第二个及后面的数据，那么j就要取i前面的数据与i相加才能避免使数据做重复的相加

　　当nums[i] + nums[j] == target 成立就可得到答案

 

167. 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.

int* twosum(int* numbers, int numberssize, int target, int* returnsize) {
    *returnsize = 2;
    int *array = null;
    for(int i = 1; i < numberssize; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(numbers[i] + numbers[j] == target)
            {
                array = (int *)malloc(*returnsize * sizeof(int));
                array[0] = j + 1;
                array[1] = i + 1;
                return array;
            }
        }
    }
    return null;
}

 

653. 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

 1 /*
 2 struct treenode 
 3 {
 4 int val;
 5 struct treenode *left;
 6 struct treenode *right;
 7 };
 8 
 9 */
10 
11 　bool findvalue(struct treenode* root, struct treenode* temp, int k)
12  {
13      if(!temp)
14       {
15           return false;
16       }
17       if(temp->val == k && temp != root)
18       {
19           return true;
20      }
21      if(k > temp->val)
22      {
23          return findvalue(root, temp->right, k);
24      }
25      else
26      {
27          return findvalue(root, temp->left, k);
28      }
29  }
30  
31  bool findx(struct treenode* root, struct treenode* temp, int k)
32  {
33      if(!root)
34      {
35          return false;
36      }
37      if(findvalue(root, temp, k - root->val))
38      {
39          return true;
40      }
41      else
42      {
43          return (findx(root->left, temp, k) || findx(root->right, temp, k));
44      }
45  }
46  
47  bool findtarget(struct treenode* root, int k) {
48      struct treenode* ptemp = root;
49      return findx(root, ptemp, k);
50 }

 

代码37行的k - root->val表示 目标数 减去 二叉树中某一个数剩下的那个数据，如果递归查找树能找到与k - root->val相等的数并且不是同一个节点的数据（第17行有做判断）说明存在两个相加等于目标的数。