Description#
Given an array of integers nums and a target value target, find two numbers in the array that add up to the target value and return their indices.
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]
Approach#
- Allocate memory.
- Fix the first index and check if there is a second index that satisfies the condition.
- Find two matching indices and return them.
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize = 2;
int* values = (int*)malloc(sizeof(int) * (*returnSize));
for(values[0] = 0;values[0] < numsSize ;values[0]++) {
for(values[1] = values[0] + 1;values[1] < numsSize ;values[1]++) {
if(nums[values[0]] + nums[values[1]] == target) {
return values;
}
}
}
return 0;
}
At first, when I saw the parameter returnSize, I thought it was not the sum of two numbers, but the sum of a given number. So I thought I needed to implement n nested for loops, but I didn't have a reasonable approach because I couldn't figure out how to write n nested for loops.
Then I looked at the solution online, which directly assumes that returnSize is 2, so I didn't worry about it and used the above method to brute force search. Currently, I haven't thought of a new way to solve it.
N Sum#
However, after writing this solution, I found that these two for loops have a pattern, so it seems that I have a way to implement n sum. It requires using recursive algorithms.
int digui(int* nums, int numsSize, int target, int* returnSize,int i,int sum,int* values,int* flag) {
// Exit condition
if(*flag == 1)
return 0;
// First time
if(i == 0) {
for(values[0] = 0;values[0] < numsSize ;values[0]++) {
sum += nums[values[0]];
digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
}
}
// Another time
else {
for(values[i] = values[i-1] + 1;values[i] < numsSize ;values[i]++) {
sum += nums[values[i]];
// Last time
if(i == *returnSize - 1) {
if(sum == target)
*flag = 1;
return 0;
}
// Not last time
else
digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
}
}
return 0;
}
In the parameters, compared to the original, there are four additional parameters: i, indicating the current nested level; sum, the sum of the previous nested levels; values, storing the index addresses; flag, the end flag. The exit condition for recursion is when it is the last number and the sum reaches the requirement. The following is the debugging code:
#include <stdio.h>
#include <malloc.h>
int digui(int* nums, int numsSize, int target, int* returnSize,int i,int sum,int* values,int* flag);
int digui(int* nums, int numsSize, int target, int* returnSize,int i,int sum,int* values,int* flag) {
// Exit condition
if(*flag == 1)
return 0;
// First time
if(i == 0) {
for(values[0] = 0;values[0] < numsSize ;values[0]++) {
sum += nums[values[0]];
digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
}
}
// Another time
else {
for(values[i] = values[i-1] + 1;values[i] < numsSize ;values[i]++) {
sum += nums[values[i]];
// Last time
if(i == *returnSize - 1) {
if(sum == target)
*flag = 1;
return 0;
}
// Not last time
else
digui(nums,numsSize,target,returnSize,i++,sum,values,flag);
}
}
return 0;
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* nSum(int* nums, int numsSize, int target, int* returnSize){
int* values = (int*)malloc(sizeof(int) * (*returnSize));
static int sum = 0,i = 0,flag = 0;
digui(nums,numsSize,target,returnSize,0,sum,values,&flag);
return values;
}
int main(void) {
static int nums[7] = {8,12,34,2,3,5,33};
static int target = 10;
static int numsSize = 7;
static int returnSize = 3;
int* value = nSum(nums,numsSize,target,&returnSize);
printf("value are %d %d %d\n",value[0],value[1],value[2]);
free(value);
return 0;
}
However, when compiling and running, I encountered an error. The following is the prompt from gdb:
The prompt indicates a pointer problem, but I don't have a solution yet, and I'm not sure where I went wrong. If anyone finds any mistakes, please leave a comment. Thank you.