Leetcode C程序,数组中两个数相加等于目标值

huangapple go评论66阅读模式
英文:

Leetcode C program, two numbers in array that add to target

问题

我正在尝试使用C语言解决一个Leetcode问题,但是出现了一个问题,我的程序输出了一个空数组。这个挑战是编写一个函数,该函数返回一个数组,其中包含两个数字的索引,这两个数字的和等于目标数字。我已经使用Python解决了这个问题,但现在我正在尝试使用C语言解决它。我错过了什么吗?是否与returnSize有关?

注意:约束条件说明每个目标数组中只会有一个答案(两个数字相加等于目标)。

我尝试过的解决方案如下:

/**
* 注意:返回的数组必须使用malloc分配内存,假定调用者会调用free()。
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* answer;
    answer = malloc(2*sizeof(int));

    // 当两个整数被识别时,成功标志会翻转
    bool success = false;

    // 遍历nums的每个元素
    for(int first_number = 0; first_number < numsSize; first_number++)
    {
        // 如果索引位于数组末尾,请不要继续检查。
        if(first_number < numsSize)
        {
            // 对数组中的每个数字,查看其后的所有数字
            for(int second_number=(first_number + 1); second_number < numsSize; second_number++)
            {
                if((nums[first_number] + nums[second_number] == target))
                {
                    answer[0] = first_number;
                    answer[1] = second_number;
                    // 翻转成功标志
                    success = true;
                }
            }
        }

        // 检查成功标志并中断。无需继续检查。
        if(success){
            break;
        }
    }

    return answer;
}

更新
由Fe2O3回答。谢谢。如果有人看到这篇帖子,请阅读Fe2O3的回答。WhozCraig还对问题进行了很好的解释。原来int *returnSize是指向存储输出数组大小的变量的指针。我猜动态分配数组的大小不能像静态分配数组(例如int returnSize[2])那样轻松确定。Fe2O3还对Leetcode答案的实现和不受标准答案限制的观点提出了一些建议。他提供了多个可行的解决方案。希望这有所帮助。

英文:

I am trying to solve a Leetcode problem using C, and for some reason the Output of my program is showing an empty array. The challenge is to write a function that returns an array consisting of the indices of two numbers in an array that sum to a target number. I solved it with Python, but now I am trying to solve it with C. What am I missing? Does it have something to do with returnSize?

Note: The constraints say there will be only one answer (two numbers that add up to the target) in each array for each target.

The solution I have tried is as follows:

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* answer;
    answer = malloc(2*sizeof(int));

    // Success flag flips when two ints are identified
    bool success = false;

    // Look through every element of nums
    for(int first_number = 0; first_number &lt; numsSize; first_number++)
    {
        // If index is at end of array, do not check further.
        if(first_number &lt; numsSize)
        {
            // For each number in array, look at all of the numbers after it
            for(int second_number=(first_number + 1); second_number &lt; numsSize; second_number++)
            {
                if((nums[first_number] + nums[second_number] == target))
                {
                    answer[0] = first_number;
                    answer[1] = second_number;
                    // Flip success flag
                    success = true;
                }
            }
        }

        // Check success flag and break. No need to check further.
        if(success){
            break;
        }
    }

    return answer;
}

<b>Update</b><br/>
Answered by Fe2O3. Thank you. If anyone comes across this post, read Fe2O3's answer. WhozCraig also gives a good explanation of the problem. It turns out int *returnSize is a pointer to a variable that stores the size of the output array. I guess the size of dynamically allocated arrays can't be determined as easily as statically allocated arrays (e.g. int returnSize[2]). Fe2O3 also has some good things to say about the implementation of the Leetcode answer and not limiting oneself to standard answers. He gave multiple solutions that work. I hope this helps.

答案1

得分: 1

以下是代码的翻译部分:

int *twoSum( int *nums, int numsSize, int target, int *returnSize ) {
	*returnSize = 0; // 默认值

	for( int i = 0; i < numsSize; i++ )
		for( int j = i + 1; j < numsSize; j++ )
			if( nums[ i ] + nums[ j ] == target ) {
				int *answer = malloc( 2 * sizeof *answer );
                /* 为了简洁起见,省略了malloc成功验证 */
				answer[0] = i;
				answer[1] = j;
                *returnSize = 2;
				return answer;
			}

	return NULL;
}

这是代码的翻译部分。请注意,翻译是直译的,没有添加任何额外的内容。

英文:

Having bitten into this apple, I feel compelled to demonstrate how this function might be written by one with more experience:

int *twoSum( int *nums, int numsSize, int target, int *returnSize ) {
	*returnSize = 0; // default

	for( int i = 0; i &lt; numsSize; i++ )
		for( int j = i + 1; j &lt; numsSize; j++ )
			if( nums[ i ] + nums[ j ] == target ) {
				int *answer = malloc( 2 * sizeof *answer );
                /* Omitting verification of malloc success for brevity */
				answer[0] = i;
				answer[1] = j;
                *returnSize = 2;
				return answer;
			}

	return NULL;
}

It's a silly (Leetcode) problem.<br>
The caller should provide the array (could be stack instead of heap allocation) for the two indices (if found). The function would "know" it can write two integer indices into that array IF a pair is located. Then the function merely returns true or false as to whether it had success or not...

EDIT<br>
Longer response to OP question below:

A minor change to the Leetcode problem might take this form. Notice that the "return array" exists on the stack in the function main() (without needing the heap allocation.) The function needs 4 parameters and returns true/false if it was able to put the two desired values into the 2 element array.

int main(){
	const int arr[] = { 1, 2, 3, 4, 9 };
	const int arrSz = sizeof arr/sizeof arr[0];
	const int target = 4 + 9; // last two values
	int inds[2] = { 0 }; // ALWAYS initialise variables

	if( twoSum( arr, arrSz, target, inds ) )
		print( &quot;[%d, %d]\n&quot;, inds[0], inds[1] );
	else
		print(&quot;Error\n&quot;);
	return 0;
}

UPDATE:<br>
Bothered by the OP reference to "future job interview questions", this answer needs to be revisited.

Below is a "general purpose" version of the function that disregards the "promise" that only one pair of array elements may satisfy the task. The following will grow the array being returned if multiple pairs are found.

Further, (and this is the "job interview" aspect), the solution should recognise that there was no restriction that each of any pair found had to be distinct. In other words, one element + its own value may be a legitimate solution. It is unwise to assume... This sensitivity and "thinking outside the box" is often what potential employers are seeking. It is the coder who thinks only "inside the box" who will introduce bugs into code.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

// 0 == allow arr[X] + arr[X] == target
// 1 == only distinct elements to be considered
#define ONLY_DIFF 1

int *twoSum( int *nums, int sz, int target, int *rs ) {
	// Begin with no pairs
	int *retArr = NULL;
	*rs = 0;

	for( int i = 0; i &lt; sz; i++ )
		for( int j = i + ONLY_DIFF; j &lt; sz; j++ )
			if( nums[ i ] + nums[ j ] == target ) {
				int *hope = realloc( retArr, (*rs + 2) * sizeof *hope );
				if( hope == NULL ) {
					fprintf( stderr, &quot;realloc failure\n&quot; );
					exit( EXIT_FAILURE );
				}
				retArr = hope;
				*rs += 2;
				retArr[ *rs - 2 ] = i;
				retArr[ *rs - 1 ] = j;
			}

	return retArr;
}

huangapple
  • 本文由 发表于 2023年1月9日 11:22:25
  • 转载请务必保留本文链接:https://go.coder-hub.com/75052898.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定