/*
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
*/#include<vector>
#include<iostream>
using namespace std;#define SUCCESS 1
#define UNSUCCESS 0
#define NULLKEY 0x7ffffffftypedef struct{int key;int val;
} Info;typedef struct{Info* info;  //数据元素存储基址，动态分配数组int count;  //当前元素个数
} HashTable;
int HashSize = 0;class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {HashSize = nums.size();HashTable *ht = new HashTable;initHashTable(ht);int val;for(int i=0; i<HashSize; i++){/* 在不考虑哈希表本身初始化消耗时间的情况下。1、先查后插入，先找到后一个元素，再从哈希表中找前一个元素，可以减少时间，时间复杂度最好为2，最坏是size。而且因为当前元素nums[i]是不在哈希表中的，不用考虑重复问题.2、如果先把所有元素插入哈希表，再查找，首先时间复杂度最好是size+1，最坏是2*size。其次还需要考虑重复问题如：[0,4,3,0]; target=0。当i=0，去查找哈希表时就会返回key=0，val=0（val是数组下标），而不是key=0，val=3；于是最后的结果就是[0, 0]*/if(searchHash(ht, (target-nums[i]), &val)){return {val, i};}insertHash(ht, nums[i], i);}}//初始化哈希表int initHashTable (HashTable *H){H->count = HashSize;H->info = new Info[sizeof(Info)*HashSize];if (H->info == NULL){return UNSUCCESS;}for(int i=0; i<HashSize; i++){H->info[i].key = NULLKEY;}return SUCCESS;}//哈希函数int hash (int key){return (key % HashSize);   //hash函数：除留余数法}//插入关键字void insertHash (HashTable *H, int key, int val){int addr = hash(key);while (H->info[addr].key != NULLKEY){   //不为空，则冲突addr = (addr+1) % HashSize;    //开发定址法线性探查}H->info[addr].key = key;    //直到有空位H->info[addr].val = val;}int searchHash (HashTable *H, int key, int *val){int addr = hash(key);while (H->info[addr].key != key){addr = (addr+1) % HashSize;if (H->info[addr].key == NULLKEY){return UNSUCCESS;}}*val = H->info[addr].val;return SUCCESS;}
};int main(){vector<int> nums = {0,4,3,0};Solution s;vector<int> arr = s.twoSum(nums, 0);cout << arr[0] << " " << arr[1] << endl;return 0;
}