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行有做判断）说明存在两个相加等于目标的数。