算法知识点————数论和链表

1、n数和

2数和

• 有序（递增）：头尾相加，和目标值比较
• 无序：哈希表（target - cur）

多数和：
​ 先排序
拿一个数（检测 i 和i-1 重复的不选择）
​ 2数和问题 （检测 去重）

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int len = nums.size();vector<vector<int>> res; //结果是一个二元组 ，每个里面是个vectorint i,j,k;sort(nums.begin(),nums.end());//先排序for(i = 0;i<len -2;i++){ //先取一个数if( i > 0 && nums[i] == nums[i-1]) continue;//去重，重复元素就不取了int temp = 0 - nums[i]; //temp记录剩下两个数和的负值int l = i+1,r = nums.size()-1;//左右指针寻找值while( l < r){int sum = nums[l] + nums[r] ;if(sum == temp)//找到了{res.push_back({nums[i],nums[l],nums[r]}); //存到结果res中while(l < r && nums[l] == nums[++l]);//去重 l向后面移动while(l < r && nums[r] == nums[--r]);}else if (sum < temp){//和不够l++;}else {r--;}}}return res;}
};

2、回文数121 回文串abcba

• 负数不是回文数字
• 个位数都是回文数
• 0结尾的数不是回文数
• 从后往前取数 %10 然后和原来的数比较
• 跳出while循环要么是num == x 要么是不等于（大于和小于）
• 最后的可能是12和1或者12和12 或者1和12都算

class Solution {
public:bool isPalindrome(int x) {if(x < 0) return false;if(x < 10) return true;if(x%10 == 0) return false;int num = 0;while(num < x){//121num = num*10 + x%10;//当前值 12x/=10;//1}if(x == num || num == x/10 || x == num/10) return true;//else return false;}
};

3、两个链表对应两个数组然后相加，结果在链表中
1->5->8 对应851
1->6->3->9 对应9361

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2,int carry =0) {if(l1 == nullptr && l2 == nullptr){return carry ? new ListNode(carry) : nullptr;//如果有进位，创建节点}if(l1 == nullptr) swap(l1,l2);//如果l1 是空的，l2一定不是空的 ，交换l1和l2保证l1非空int sum = carry+l1->val+(l2 ? l2->val :0);l1->val = sum%10;//节点保存数位l1->next = addTwoNumbers(l1->next,(l2 ? l2->next : nullptr),sum / 10);return l1;}
};

升级版本：两次反转链表，然后相加，结果返回反转

1->5->8 对应158
1->6->3->9 对应1639

class Solution {
public:ListNode* reverseList(ListNode* head){if(head == nullptr || head->next == nullptr) return head;auto newNode = reverseList(head->next);head->next->next = head;head->next = nullptr;return newNode;}ListNode *addTwo(ListNode* l1,ListNode* l2 ,int carry = 0){if(l1 == nullptr && l2 == nullptr){return carry ? new ListNode(carry) :nullptr;}if(l1 == nullptr) swap(l1,l2);carry += l1->val + (l2 ? l2->val : 0);l1->val = carry %10;l1->next = addTwo(l1->next ,(l2 ? l2->next : nullptr),carry/10);return l1;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//两次反转链表，然后相加，结果返回反转l1 = reverseList(l1);l2 = reverseList(l2);auto l3 = addTwo(l1,l2);return reverseList(l3);}
};