【力扣】1、两数之和

力扣(LeetCode)刷题

【力扣】1、两数之和

---

文章目录

• 力扣(LeetCode)刷题
• 前言
• 
  

  一、题目

• 
  

  二、题解

• • 1.双指针法
  • 2.暴力法
  • 3.散列法
  • 4.排序查找法
• 总结

---

前言

    最近疫情又开始严重了起来，宅在家里太无聊了，闲着也是闲着，刷刷力扣玩。

由于是练习算法，所以我更倾向于用C语言来实现，我对C语言的用法还停留在大学，如果有哪里写的不对的地方也欢迎各位小伙伴提出

---

一、题目

    码云
    先来看下题目

    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标

你可以假设每种输入只会对应一个答案。

但是，数组中同一个元素不能使用两遍

你可以按任意顺序返回答案

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

二、题解

    这个题目主要有四种解法，如下：

1.双指针法

    这个解法是参考力扣评论里的方法，这里就叫它双指针法吧。

不过效率有点慢，运行了几次只超过了 5%的用户，在这里也列举一下吧

#include 
#include 

/**
 * 双指针法
 * @param nums
 * @param numSize
 * @param target
 * @param returnSize
 * @return
 */
int *twoSum(int *nums, int numSize, int target, int *returnSize) {
    int slow = 0;
    int quick = 1;
    while (quick < numSize) {
        if (nums[slow] + nums[quick] == target) {
            *returnSize = 2;
            int *ret = (int *) malloc(sizeof(int) * 2);
            ret[0] = slow;
            ret[1] = quick;
            return ret;
        }
        if (quick == numSize - 1) {
            slow += 1;
            quick = slow + 1;
        } else {
            quick += 1;
        }
    }
    *returnSize = 0;
    return NULL;
}

2.暴力法

    这个题目最直观的解法就是直接双循环，计算结果和目标值进行比较。

不过这里可以做一点小小的优化，由于第一层已经循环过的没必要再循环一次，所以第二层循环从第一层的下标位置+1开始循环即可。

这个解法用时大约击败50%左右的用户。

代码如下：

/**
 * 暴力法
 * @param nums
 * @param numSize
 * @param target
 * @param returnSize
 * @return
 */
int *twoSum(int *nums, int numSize, int target, int *returnSize) {
    for (int i = 0; i < numSize; ++i) {
        for (int j = i + 1; j < numSize; ++j) {
            if (target == nums[i] + nums[j]) {
                *returnSize = 2;
                int *ret = (int *) malloc(sizeof(int) * 2);
                ret[0] = i;
                ret[1] = j;
                return ret;

            }
        }
    }
    *returnSize = 0;
    return NULL;
}

3.散列法

    散列法主要就是采取空间换时间的方式来提高执行效率，利用一个map，对数组值和下标进行存储，值为key，下标为value，就不需要进行二次遍历了。

由于题目说的是：数组中同一个元素在答案里不能重复出现，所以不会存在覆盖的问题，这个解法大概击败85%左右的用户。

由于C语言没有现成的HashMap给我们用，这里只能自己实现一个拙劣的HashMap了

    先申明一个table.h，用来指定map的结构和方法，代码如下：

#ifndef LEET_CODE_TABLE_H
#define LEET_CODE_TABLE_H
#define TABLE_DEFAULT_SIZE 10


typedef struct entry {
    int key;
    int val;
    struct entry *next;
} Entry;
typedef struct table {
    Entry **nodes;

    Entry *(*get)(struct table *ht, int key);

    int (*put)(struct table *ht, int key, int val);//定义函数指针
    void (*clear)(struct table *ht);
} HashTable;

Entry *get(HashTable *ht, int key);

HashTable *create();

void clear(HashTable *ht);

int put(HashTable *ht, int key, int val);

unsigned int hash(int key);

#endif //LEET_CODE_TABLE_H

    再来一个table.c具体实现它，代码如下：

#include 
#include "table.h"

HashTable *create() {
    HashTable *table = NULL;
    size_t size = sizeof(Entry) * TABLE_DEFAULT_SIZE;
    table = malloc(sizeof(HashTable));
    table->nodes = malloc(size);
    for (int i = 0; i < TABLE_DEFAULT_SIZE; i++) {
        table->nodes[i] = NULL;  // 初始化
    }
    table->get = get;
    table->put = put;
    table->clear = clear;
    return table;
}

Entry *get(HashTable *ht, int key) {
    // 计算索引
    unsigned int index = hash(key);
    return ht->nodes[index];
}

unsigned int hash(int key) {
    unsigned int hash = 5381;
    hash += (hash << 5) + key;
    return (hash & 0x7FFFFFFF) % TABLE_DEFAULT_SIZE;
}


int put(HashTable *ht, int key, int val) {

    // 计算下标
    unsigned int index = hash(key);


    Entry *newNode = malloc(sizeof(Entry));
    newNode->key = key;
    newNode->val = val;
    newNode->next = NULL;

    if (ht->nodes[index] == NULL) {
        ht->nodes[index] = newNode;  // 无冲突
    } else {
        /**
         * 值一样，不 *** 作
         */
        if (ht->nodes[index]->val == val) {
            free(newNode);
            newNode = NULL;
            return 0;
        }
        // 有冲突
        Entry *node = ht->nodes[index];
        while (node->next != NULL) {
            node = node->next;  // 迭代
        }
        node->next = newNode;  // 给链表赋值
    }
    return 1;
}

void clear(HashTable *ht) {
    if (ht != NULL) {
        for (int i = 0; i < TABLE_DEFAULT_SIZE; i++) {
            Entry *node = ht->nodes[i];
            if (node != NULL) {
                Entry *tmp = node;
                while (node->next != NULL) {
                    tmp = node->next;
                    free(node);
                    node = tmp;
                }
            }
        }
        free(ht->nodes);
        ht->nodes = NULL;
        ht->get = NULL;
        ht->put = NULL;
        ht->clear = NULL;
        free(ht);
        ht = NULL;
    }
}

    然后就可以用table实现散列解法了，代码如下：

nt *twoSum(int *nums, int numSize, int target, int *returnSize) {

    HashTable *map = create();
    for (int i = 0; i < numSize; ++i) {
        int num = target - nums[i];
        Entry *node = map->get(map, num);
        if (node != NULL) {
            while (node != NULL) {
                if (node->val != i && (nums[i] + node->key == target)) {
                    *returnSize = 2;
                    int *ret = (int *) malloc(sizeof(int) * 2);
                    ret[0] = i;
                    ret[1] = node->val;
                    map->clear(map);
                    return ret;
                }
                node = node->next;
            }
        }
        map->put(map, nums[i], i);
    }
    *returnSize = 0;
    map->clear(map);
    return NULL;
}
    

4.排序查找法

    这个方法，主要思想是先对数组进行排序，然后在利用算法提高查找效率。

这个解法大概击败90%左右的用户

    先申明一个sort.h，代码如下：

#ifndef LEET_CODE_SORT_H
#define LEET_CODE_SORT_H


int *mergeSort(int *nums, int numsSize);

void merge(int *nums, int left, int mid, int right, int *temp);

void sort(int *nums, int numsSize, int left, int right, int *temp);

int search(int *nums, int numsSize, int goal);

int getIndex(int *nums, int numsSize, int goal, int from);

#endif //LEET_CODE_SORT_H

    再来一个sort.c具体实现它，代码如下：

#include 
#include "sort.h"


int search(int *nums, int numsSize, int goal) {
    int low = 0;
    int high = numsSize - 1;
    if (nums[high] < goal || nums[low] > goal) {
        return -1;
    }
    int mid;
    while (low <= high) {
        mid = (high + low) >> 1;
        if (nums[mid] > goal) {
            high = mid - 1;
        } else if (nums[mid] < goal) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

int getIndex(int *nums, int numsSize, int goal, int from) {
    for (int i = from; i < numsSize; ++i) {
        if (nums[i] == goal) {
            return i;
        }
    }
    return -1;
}

int *mergeSort(int *nums, int numsSize) {
    int *temp = (int *) malloc(sizeof(int) * numsSize);
    int *copy = (int *) malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; ++i) {
        copy[i] = nums[i];
    }
    sort(copy, numsSize, 0, numsSize - 1, temp);
    free(temp);
    temp = NULL;
    return copy;
}

void sort(int *nums, int numsSize, int left, int right, int *temp) {

    if (left < right) {
        int mid = (left + right) / 2;
        sort(nums, numsSize, left, mid, temp);
        sort(nums, numsSize, mid + 1, right, temp);
        merge(nums, left, mid, right, temp);
    }
}

void merge(int *nums, int left, int mid, int right, int *temp) {
    int i = left;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j]) {
            temp[index++] = nums[i++];
        } else {
            temp[index++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[index++] = nums[i++];
    }
    while (j <= right) {
        temp[index++] = nums[j++];
    }
    index = 0;
    while (left <= right) {
        nums[left++] = temp[index++];
    }
}

    然后就可以用sort实现排序查找解法了，代码如下：

int *twoSum(int *nums, int numSize, int target, int *returnSize) {
    int *sort = mergeSort(nums, numSize);
    for (int i = 0; i < numSize; ++i) {
        int goal = target - nums[i];
        int index = search(sort, numSize, goal);
        if (index != -1) {
            int sourceIndex = getIndex(nums, numSize, goal, i + 1);
            if (sourceIndex != -1) {
                *returnSize = 2;
                int *ret = (int *) malloc(sizeof(int) * 2);
                ret[0] = i;
                ret[1] = sourceIndex;
                return ret;
            }
        }
    }
    *returnSize = 0;
    free(sort);
    sort = NULL;
    return NULL;
}
    

    这里排序算法使用的是归并排序，查找算法使用的是二分查找。

其他的排序查找算法这里没有进行测试，有兴趣的小伙伴可以自己去试试看

---

总结

    以上就是我所知道的两数之和解法，如果还有其他解法欢迎各位小伙伴提出