今天陪老姐送对象去安庆了,上午还去了西风禅寺求了个签,第一次拿到中评签,看来今年还需要继续努力哈哈哈。一直到晚上才有时间去做点题目,今天依旧是leetcode。
(两数之和)[https://leetcode-cn.com/problems/two-sum/]
还是一样,我们先考虑一下朴素做法,显然是双重遍历,时间复杂度是O(N^2^)
,显然在1e5
的情况下是过不掉的,所以我们选择优化到O(N)
。由于我们只需要找到一个符合题意得解即可,我们可以利用哈希表的特点边遍历边读入,这样的时间复杂度是最小的。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> hash; int len = nums.size(); for(int i = 0; i < len; ++ i){ int t = target - nums[i]; if(hash.count(t)) return {hash[t], i}; hash[nums[i]] = i; } return {}; } };
(两数相加)[https://leetcode-cn.com/problems/add-two-numbers/]
其实就是链表的模拟题。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* res = new ListNode(-1); ListNode* temp = new ListNode; res = temp; int carry = 0; while(l1 || l2){ int n1 = l1 ? l1->val : 0; int n2 = l2 ? l2->val : 0; int sum = n1 + n2 + carry; carry = sum / 10; temp->next = new ListNode(sum % 10); temp = temp->next; if(l1) l1 = l1->next; if(l2) l2 = l2->next; } if(carry) temp->next = new ListNode(1); return res->next; } };
(截断数组)[https://www.acwing.com/problem/content/4300/]
用一个前缀数组一个后缀数组来维护值就行了,需要注意的是题目要求从中间切开所以中间的数组长度绝对不为0,所以双指针的l
与r
不能相碰。
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int arr[N]; long long pre[N], last[N];//预加载前后缀和数组 int main(){ int n; cin.tie(0); ios::sync_with_stdio(false); cin >> n; for(int i = 0;i < n; ++i){ cin >> arr[i]; } for(int i = 1; i <= n; ++ i){ pre[i] = pre[i - 1] + arr[i - 1]; } for(int i = n; i >= 1; -- i){ last[i] = last[i + 1] + arr[i - 1]; } int l = 1, r = n; long long res = 0; while(l < r){ if(pre[l] > last[r]){ r--; }else if(pre[l] < last[r]) { l++; }else{ res = max(res, pre[l]); l++; } } cout << res; }