leetcode两数之和c语言

以下是 LeetCode 上的「1. 两数之和」题目的 C 语言解法：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, j;
    int* result = (int*)malloc(sizeof(int) * 2);
    for(i = 0; i < numsSize; i++){
        for(j = i+1; j < numsSize; j++){
            if(nums[i] + nums[j] == target){
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    return NULL;
}

这个解法的基本思路是：两重循环，枚举所有可能的数对，判断它们的和是否等于目标值。时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。虽然时间复杂度较高，但是这个解法比较简单易懂，可以作为其他解法的参照。

相关问题

leetcode两数之和c语言哈希表实现

以下是 LeetCode 上的「1. 两数之和」题目的 C 语言哈希表实现：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, j;
    int* result = (int*)malloc(sizeof(int) * 2);
    int* hashTable = (int*)malloc(sizeof(int) * numsSize);
    memset(hashTable, -1, sizeof(int) * numsSize);
    for(i = 0; i < numsSize; i++){
        int complement = target - nums[i];
        if(hashTable[complement] != -1){
            result[0] = hashTable[complement];
            result[1] = i;
            *returnSize = 2;
            free(hashTable);
            return result;
        }
        hashTable[nums[i]] = i;
    }
    free(hashTable);
    return NULL;
}

这个解法的基本思路是：使用哈希表以空间换时间，保存已经遍历过的数及其下标。对于每一个数，计算其与目标值之间的差值，然后在哈希表中查找是否存在该差值，如果存在则返回两个数的下标。时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。虽然空间复杂度较高，但是时间复杂度更低，是较优的解法。

leetcode两数相加 完整代码 c语言

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    int carry = 0;
    
    while(l1 != NULL || l2 != NULL){
        int n1 = (l1 != NULL) ? l1->val : 0;
        int n2 = (l2 != NULL) ? l2->val : 0;
        int sum = n1 + n2 + carry;
        carry = sum / 10;
        
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = sum % 10;
        newNode->next = NULL;
        
        if(head == NULL){
            head = newNode;
            tail = newNode;
        }else{
            tail->next = newNode;
            tail = newNode;
        }
        
        if(l1 != NULL){
            l1 = l1->next;
        }
        if(l2 != NULL){
            l2 = l2->next;
        }
    }
    
    if(carry > 0){
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = carry;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    
    return head;
}

这是leetcode题目“两数相加”的完整C语言解法。首先定义了一个结构体`ListNode`来表示单链表的结点。然后，我们使用头尾指针`head`和`tail`来创建新的结果链表。我们还定义了一个变量`carry`来保存进位值。

在循环中，我们分别取出两个链表当前结点的值，并与进位值相加。如果链表的长度不一致，我们使用0来代替较短链表的缺失结点值。然后，我们将求和结果的个位数作为新结点的值，并更新进位值。

接着，我们创建新结点并将其加入结果链表中。第一个新结点既是头指针也是尾指针，而后续新结点都仅作为尾指针的next指向。

最后，如果进位值大于0，我们将其作为新结点加入结果链表的尾部。

最后返回头指针head即可。