Leetcode

1.两数之和

题目链接：1. 两数之和 - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

暴力：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i = 0, j =0;
        for(i = 0; i < nums.size(); i++){
            for(j = i + 1; j < nums.size(); j++){
                if(nums[i] + nums[j] == target){
                    return{i,j};
                }
            }
        }
        return{i,j};     
    };
};

标程：哈希表应用

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> m;
        for(int i = 0; i < nums.size(); i++) {
            if(m.find(target-nums[i]) != m.end()) {
                res.push_back(i);
                res.push_back(m[target-nums[i]]);
                break;
            }
            m[nums[i]] = i;
        }
        return res;
    }
};

哈希表

哈希表是一种常见的数据结构，它提供键(key)到值(value)的映射。哈希表通过哈希函数将键映射到一个索引，然后将值存储在该索引位置的数组中，从而实现快速的查找和插入操作。

哈希函数将任意长度的输入映射为固定长度的输出。哈希函数应该具有以下两个特点：

1. 性能高效：哈希函数应该能够在常数时间内计算得出哈希值，从而使查询和插入的时间复杂度为O(1)。

2. 均匀性：哈希函数应尽可能均匀地分配输入，从而使哈希表的空间能够被合理利用。

使用哈希表进行查找操作时，首先需要计算给定key的哈希值，然后通过该哈希值获取数组中的索引位置，最后在该索引位置上查找对应的值。当多个key映射到同一索引位置时，哈希表通常使用链表或树结构来解决冲突。

哈希表的时间复杂度为O(1)，在查找和插入操作上都表现出非常高的性能。所以，在需要快速查找和插入的场景中，哈希表是一种常用的数据结构。

下面是一个简单的C++实现的哈希表程序，它可以插入、查找和删除记录。注意，这里使用了链地址法来解决哈希冲突。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class HashTable {
private:
    vector<pair<int,int>> table[100]; // 存储哈希表的数组
    int hash(int key) { return key % 100; } // 哈希函数：对key取模
public:
    void insert(int key, int value) {
        int index = hash(key);
        for (auto& p : table[index]) {
            if (p.first == key) { // 如果key已经存在，则更新value
                p.second = value;
                return;
            }
        }
        // 如果不存在，则插入新记录
        table[index].emplace_back(key, value);
    }

    int find(int key) {
        int index = hash(key);
        for (auto& p : table[index]) {
            if (p.first == key) { // 查找到key对应的记录
                return p.second;
            }
        }
        return -1; // 没有找到
    }

    void remove(int key) {
        int index = hash(key);
        table[index].erase(
            remove_if(table[index].begin(), table[index].end(),
                      [key](const pair<int,int>& p) { return p.first == key; }),
            table[index].end()
        );
    }
};

int main() {
    HashTable ht;
    ht.insert(1, 10);
    ht.insert(2, 20);
    ht.insert(3, 30);
    cout << ht.find(1) << endl; // 10
    cout << ht.find(2) << endl; // 20
    cout << ht.find(4) << endl; // -1
    ht.remove(2);
    cout << ht.find(2) << endl; // -1
    return 0;
}

该程序使用了一个长度为100的vector数组来存储哈希表记录。哈希函数是简单的对key取模。如果发生哈希冲突，即多个key映射到同一个索引位置，则使用链表记录这些key-value对。

insert函数在table中查找给定key是否已存在，如果存在则更新value，如果不存在则将新的key-value对插入到链表中。

find函数也是通过hash函数计算给定key的索引位置，然后在对应的链表中查找给定的key是否存在。如果不存在则返回-1。

remove函数也是通过hash函数计算给定key的索引位置，在对应的链表中查找并删除key-value对。