CS110L-#01: Welcome to CS 110L

第一节 Welcome to CS 110L

视频:

Slides:https://reberhardt.com/cs110l/spring-2020/slides/lecture-01.pdf

笔记

1.为什么使用Rust

2.为什么不是用C/C++?

安全问题:

例子程序:https://www.tutorialspoint.com/convert-a-string-to-uppercase-in-c

看了一下,程序的作用是把字符串转成大写,明显gets存在缓冲区溢出。在编译的时候,编译器也提醒了。

➜  01 git:(main) ✗ ./a.out 

Enter a string:ashdasihdddddddddddddddddddddddddddddddddddddddddddddddddddddddd

String in Upper Case = ASHDASIHDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD%                                              
➜  01 git:(main) ✗ ./a.out

Enter a string:GgaudiasSSSSSSSSSASUGDAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

*** stack smashing detected ***: terminated
[1]    18336 abort      ./a.out

很明显,C/C++的内存安全的问题很严重,这其实也是众所周知的,老师还提到一篇论文,关于汽车攻击面的。

论文:http://www.autosec.org/pubs/cars-usenixsec2011.pdf

YouTube解读: https://www.youtube.com/watch?v=bHfOziIwXic

还提到Chrome OS中的一个 one byte overflow and symlinks,DNS库的一个字节的溢出

链接: https://googleprojectzero.blogspot.com/2016/12/chrome-os-exploit-one-byte-overflow-and.html

然后老师讨论缓冲区溢出的问题,举了一个例子:

char buffer[128];
int bytesToCopy = packet.length;
if (bytesToCopy < 128) {
 strncpy(buffer, packet.data, bytesToCopy);
}

看起来是有边界检查的,也使用了带有长度的strncpy函数。但是其实strncpy也是有问题的,容易产生空字符结尾错误和其他的问题。

但是这里的问题,其实是整数转换的问题。

C/C++的内存安全问题,也有很多人搞了一些工具来检查。主要是动态分析和静态分析,动态分析需要预测输入,静态分析主要是错误非常多。

比如: valgrind

我用valgrind来跑convert程序,看看会出什么样的结果

➜  01 git:(main) ✗ valgrind --tool=memcheck --leak-check=full ./conver
==2022== Memcheck, a memory error detector
==2022== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2022== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==2022== Command: ./conver
==2022==

Enter a string:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

*** stack smashing detected ***: terminated
==2022==
==2022== Process terminating with default action of signal 6 (SIGABRT)
==2022==    at 0x489C18B: raise (raise.c:51)
==2022==    by 0x487B858: abort (abort.c:79)
==2022==    by 0x48E63ED: __libc_message (libc_fatal.c:155)
==2022==    by 0x4988B49: __fortify_fail (fortify_fail.c:26)
==2022==    by 0x4988B15: __stack_chk_fail (stack_chk_fail.c:24)
==2022==    by 0x109245: main (convert.c:22)
String in Upper Case = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA==2022==
==2022== HEAP SUMMARY:
==2022==     in use at exit: 0 bytes in 0 blocks
==2022==   total heap usage: 2 allocs, 2 frees, 2,048 bytes allocated
==2022==
==2022== All heap blocks were freed -- no leaks are possible
==2022==
==2022== For lists of detected and suppressed errors, rerun with: -s
==2022== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
[1]    2022 abort      valgrind --tool=memcheck --leak-check=full ./conver

其实valgrind检查不了这种缓冲区溢出的漏洞。

3.为什么不是用其他有GC的语言?

GC 有性能问题,垃圾一般都是丢在你家里,收集垃圾的需要敲你的门来收集垃圾。

  • 代价昂贵
  • 具有破坏性
  • 存在非确定性
  • 排除了手动优化的可能

需要程序都需要高性能,比如

  • 用户界面程序
  • 游戏
  • 自动驾驶
  • 支付处理
  • 高频交易

4.预习

找bug,链接: https://web.stanford.edu/class/cs110l/lecture-notes/lecture-02/

解答:

程序如下

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// There are at least 7 bugs relating to memory on this snippet.
// Find them all!

// Vec is short for "vector", a common term for a resizable array.
// For simplicity, our vector type can only hold ints.
typedef struct {
  int* data;     // Pointer to our array on the heap
  int  length;   // How many elements are in our array
  int  capacity; // How many elements our array can hold
} Vec;

Vec* vec_new() {
  Vec vec;
  vec.data = NULL;
  vec.length = 0;
  vec.capacity = 0;
  return &vec;
}

void vec_push(Vec* vec, int n) {
  if (vec->length == vec->capacity) {
    int new_capacity = vec->capacity * 2;
    int* new_data = (int*) malloc(new_capacity);
    assert(new_data != NULL);

    for (int i = 0; i < vec->length; ++i) {
      new_data[i] = vec->data[i];
    }

    vec->data = new_data;
    vec->capacity = new_capacity;
  }

  vec->data[vec->length] = n;
  ++vec->length;
}

void vec_free(Vec* vec) {
  free(vec);
  free(vec->data);
}

void main() {
  Vec* vec = vec_new();
  vec_push(vec, 107);

  int* n = &vec->data[0];
  vec_push(vec, 110);
  printf("%d\n", *n);

  free(vec->data);
  vec_free(vec);
}

运行:

[1] 4278 segmentation fault ./pre

直接段错误

7处错误:

  1. 在vec_new中,创建了一个局部变量vec,并返回了&vec
  2. vec.data 应该是vec->data = NULL
  3. vec_push中不要使用assert
  4. vec_push中vec->length没有检查,而且可以设置为unsigned
  5. free(vec->data)错误
  6. vec_free中应该先free(vec->data)
  7. vec_push 中 ++vec->length错误

第一周的作业

作业链接:

[rust-ctf] VolgaCTF 2017 Quals: Transformer

VolgaCTF 2017 Quals: Transformer

链接: https://ctftime.org/task/3695

题目:transformer

We’ve got a file that was processed with a binary called transformer. We really need the contents of this file. Can you help?


开始探索

在Mac上执行程序:


[Transformer] ./transformer zsh: exec format error: ./transformer


使用file 查看 文件属性
[Transformer] file transformer transformer: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=3ba9baed5d1738eef040f333ec9c4707c3aeabf4, with debug_info, not stripped


发现是 64 位 Linux 二进制文件,拿到Linux系统下运行

➜ Transformer git:(main) ✗ ./transformer Usage: transformer <input_file> <output_file>

使用ldd 看看调用的库
➜ Transformer git:(main) ✗ ldd ./transformer linux-vdso.so.1 (0x00007ffc0c1ed000) libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007fdccaf82000) librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007fdccaf77000) libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007fdccaf55000) libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007fdccaf3b000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fdccad76000) /lib64/ld-linux-x86-64.so.2 (0x00007fdccb1f5000)

我们尝试调用一下这个程序,构造一个输入文件:


➜ Transformer git:(main) ✗ ./transformer input.txt output.txt ➜ Transformer git:(main) ✗ cat input.txt output.txt 123456 uV���7�#


123456 输入,输出的内容看不懂,有乱码, 文件类型为data,文件大小由7 bit变成了12 bit

用IDA打开二进制文件

0797.All Paths From Source to Target

797. All Paths From Source to Target

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length – 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0—>1
| |
v v
2—>3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

思路

这题直接DFS,递归遍历就好了

  • 时间复杂度 O(N)
  • 空间复杂度 O(N)

代码

pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {


let mut paths = Vec::with_capacity(graph.len());
let mut path = Vec::with_capacity(graph.len());

path.push(0);

find_N(0,&mut path,&mut paths,&graph);

return paths;
}

pub fn find_N(poient:i32,mut path:&mut Vec<i32>,mut paths:&mut Vec<Vec<i32>>,graph:&Vec<Vec<i32>>){
if poient == (graph.len()-1) as i32 {
paths.push(path.clone());
}
else {
for next in &graph[poient as usize]{
path.push(*next);
find_N(*next,&mut path,&mut paths,& graph);
path.pop();
}
}
}
  • 执行用时: 12 ms
  • 内存消耗: 2.4 MB

题型与相似题

题型

1.DFS
2.graph

相似题

代码链接

all_paths_from_source_to_target

0706. Design HashMap

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // returns 1
hashMap.get(3); // returns -1 (not found)
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1
hashMap.remove(2); // remove the mapping for 2
hashMap.get(2); // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

思路

设计一个HashMap的几点:

  • 设计一个合适的散列函数;
  • 定义装载因子阈值,并且设计动态扩容策略;
  • 选择合适的散列冲突解决方法。

工业级的HashMap主要采用链表法,有的库为了优化还采用红黑树。

这里就粗暴的用两个链表来实现。

  • 时间复杂度 O(N)
  • 空间复杂度 O(N)

代码

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Clone, Debug)]
pub struct MyLinkedList {
len: i32,
head: Option<Rc<RefCell<Node>>>,
tail: Option<Rc<RefCell<Node>>>,
}

#[derive(Clone, Debug)]
struct Node {
pub key: i32,
pub val: i32,
pub prev: Option<Weak<RefCell<Node>>>,
pub next: Option<Rc<RefCell<Node>>>,
}

impl Node {
pub fn new(key: i32, val: i32) -> Self {
Node {
key,
val,
prev: None,
next: None,
}
}
}


impl MyLinkedList {
pub fn new() -> Self {
let ret = MyLinkedList {
len: 0,
head: Some(Rc::new(RefCell::new(Node::new(0, 0)))),
tail: Some(Rc::new(RefCell::new(Node::new(0, 0)))),
};
ret.head.as_ref().unwrap().borrow_mut().next = ret.tail.clone();
ret.tail.as_ref().unwrap().borrow_mut().prev = Some(Rc::downgrade(ret.head.as_ref().unwrap()));
ret
}

pub fn push(&mut self, key: i32, val: i32) {
if let Some(p) = self.find_by_key(key) {
p.borrow_mut().val = val;
return;
}

let p = self.tail.clone().unwrap();
let p = p.borrow().prev.as_ref().unwrap().upgrade().clone().unwrap();


let next = p.borrow().next.clone().unwrap();
let prev = p;


let node = Rc::new(RefCell::new(Node::new(key, val)));
node.borrow_mut().prev = Some(Rc::downgrade(&prev));
node.borrow_mut().next = Some(next.clone());

next.borrow_mut().prev = Some(Rc::downgrade(&node));
prev.borrow_mut().next = Some(node);

self.len += 1;
}

#[inline]
fn find_by_key(&self, key: i32) -> Option<Rc<RefCell<Node>>> {
let mut p = self.head.clone().unwrap();
for _ in 0..self.len {
let next = p.borrow().next.clone().unwrap();
p = next;
if p.borrow().key == key {
return Some(p);
}
}
None
}

pub fn get(&self, key: i32) -> i32 {
self.find_by_key(key).map(|p| p.borrow().val).unwrap_or(-1)
}

pub fn remove_by_key(&mut self, key: i32) {
if let Some(p) = self.find_by_key(key) {
let prev = p.borrow().prev.as_ref().unwrap().upgrade().clone().unwrap();
let next = p.borrow().next.clone().unwrap();

prev.borrow_mut().next = Some(next.clone());
next.borrow_mut().prev = Some(Rc::downgrade(&prev));
self.len -= 1;
}
}
}


struct MyHashMap {
map: Vec<Option<MyLinkedList>>,
}

/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyHashMap {

/** Initialize your data structure here. */
fn new() -> Self {

Self {
map: vec![None; 1001],
}
}


/** value will always be non-negative. */
fn put(&mut self, key: i32, value: i32) {

let idx = (key % 1001) as usize;
if self.map[idx].is_none() {
self.map[idx] = Some(MyLinkedList::new());
}
self.map[idx].as_mut().unwrap().push(key, value);

}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
fn get(&self, key: i32) -> i32 {
let idx = (key % 1001) as usize;
match self.map[idx].as_ref() {
None => -1,
Some(sub_map) => sub_map.get(key)
}
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
fn remove(&mut self, key: i32) {
let idx = (key % 1001) as usize;
if let Some(sub_map) = self.map[idx].as_mut() {
sub_map.remove_by_key(key);
}
}
}
  • 执行用时: 36 ms
  • 内存消耗: 4.6 MB

题型与相似题

题型

1.哈希表

相似题

代码链接

design_hashmap

0344. Reverse String

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
Example 2:

Input: [“H”,”a”,”n”,”n”,”a”,”h”]
Output: [“h”,”a”,”n”,”n”,”a”,”H”]

思路

题意来讲就是在字符数组中原地前后交换,这里我也采用了异或来做。

但是严格来讲,在这里用异或是错误的。在工程中不允许出现这样的代码。

推荐一篇文章:用异或来交换两个变量是错误的

  • 时间复杂度 O(N)
  • 空间复杂度 O(1)

代码


impl Solution {
pub fn reverse_string(s: &mut Vec<char>) {

let n = s.len();

if n == 0 {
return;
}

for i in 0..n/2 {
let j = n -1 -i;
s[i] = ((s[i] as u8) ^ (s[j] as u8)) as char;
s[j] = ((s[i] as u8) ^ (s[j] as u8)) as char;
s[i] = ((s[i] as u8) ^ (s[j] as u8)) as char;
}
}
}
  • 执行用时: 28 ms
  • 内存消耗: 5.3 MB

题型与相似题

题型

1.字符串
2.双指针

相似题

代码链接

reverse_string

0232. Implement Queue using Stacks

0232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

思路

根据题意,使用栈来实现一个队列。先进后出实现先进先出。

这里有提示,如果使用的语言没有实现Stack,就用队列。Python如果使用list来实现队列就非常的简单(算作弊)

这题的基本思路就是使用两个栈,但是具体的操作需要看实现。

可以在入队时变为FIFO,也可以在出队时变为FIFO。

入队如果变FIFO,那么在新进元素的时需要放在栈底,我们只能用另外一个栈暂存元素,放置之后再放回来。

  • 时间复杂度 O(N)
  • 空间复杂度 O(1)

出队如何变FIFO,那么使用另外一个栈暂存元素,把栈底元素弹出。

  • 时间复杂度 O(1) 最坏O(N)
  • 空间复杂度 O(1)

代码

struct MyQueue {
vec1: Vec<i32>,
vec2: Vec<i32>,
}


/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyQueue {

/** Initialize your data structure here. */
fn new() -> Self {

MyQueue {
vec1: Vec::new(),
vec2: Vec::new(),
}
}

/** Push element x to the back of queue. */
fn push(&mut self, x: i32) {

while let Some(v) = self.vec1.pop() {
self.vec2.push(v);
}
self.vec2.push(x);
while let Some(v) = self.vec2.pop(){
self.vec1.push(v);
}
}

/** Removes the element from in front of queue and returns that element. */
fn pop(&mut self) -> i32 {

self.vec1.pop().unwrap()
}

/** Get the front element. */
fn peek(&self) -> i32 {
*self.vec1.last().unwrap()

}

/** Returns whether the queue is empty. */
fn empty(&self) -> bool {
self.vec1.is_empty()

}
}
  • 执行用时: 0 ms
  • 内存消耗: 2.1 MB

题型与相似题

题型

1.栈
2.队列

相似题

代码链接

implement_queue_using_stacks

1037. Valid Boomerang

1037. Valid Boomerang

A boomerang is a set of 3 points that are all distinct and not in a straight line.

Given a list of three points in the plane, return whether these points are a boomerang.

Example 1:

Input: [[1,1],[2,3],[3,2]]
Output: true

Example 2:

Input: [[1,1],[2,2],[3,3]]
Output: false

Note:
1.points.length == 3
2.points[i].length == 2

3.0 <= points[i][j] <= 100

思路

拿到题目先画图

我们来理解题意,首先回旋镖的意思见 回旋镖

根据题意,三个点组成两条直线,两条直线需要有一定的夹角,能组成三角形就满足条件。

那反过来,如果两条直线斜率相同,那就不能组成三角形。

解法:

斜率 k = (y2-y1) / (x2-x1)

伪代码:

return K(AB) != K(BC)

代码:

return (points[1][1]-points[0][1]) / (points[1][0]-points[0][0]) != (points[2][1]-points[1][1]) / (points[2][0]-points[1][0]);

注意算斜率是除法,我们需要考虑除0的情况。两边同时乘以两个除数,把除法转换为乘法。

C++

class Solution {
public:
bool isBoomerang(vector<vector<int>>& points) {
return (points[1][1]-points[0][1]) * (points[2][0]-points[1][0]) != (points[2][1]-points[1][1]) * (points[1][0]-points[0][0]);
}
};

Rust

impl Solution {
pub fn is_boomerang(points: Vec<Vec<i32>>) -> bool {
return (points[1][1]-points[0][1]) * (points[2][0]-points[1][0]) != (points[2][1]-points[1][1]) * (points[1][0]-points[0][0]);
}
}

0002.Add Two Numbers

0002.Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路

大数加法的思路,这里只是把存储从数组变成了链表。

从末尾开始加,超过10就进位,主要是注意边界条件,两个链表各自为空的情况

  • 时间复杂度 O(maxlen)
  • 空间复杂度 O(maxlen)

代码

impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {

let (mut l1, mut l2) = (l1,l2);
let mut dummy_head = Some(Box::new(ListNode::new(0)));
let mut tail = &mut dummy_head;
let (mut l1_end, mut l2_end, mut overflow) = (false,false,false);

loop {
let l1_value = match l1 {
Some(node) => { l1 = node.next; node.val},
None => { l1_end = true; 0},
};
let l2_value = match l2 {
Some(node) => { l2 = node.next; node.val},
None => { l2_end = true; 0},
};

if l1_end && l2_end && !overflow {
break dummy_head.unwrap().next
}

let sum = l1_value + l2_value + if overflow { 1 } else { 0 };
let sum = if sum >= 10 { overflow=true; sum -10} else {
overflow=false; sum
};

tail.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum)));
tail = &mut tail.as_mut().unwrap().next
}
}
}
  • 执行用时: 0 ms
  • 内存消耗: 2.1 MB

题型与相似题

题型

  1. 链表
  2. 大数运算

相似题

代码

add_two_numbers

0001. Two Sum

0001. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

  1. 暴力 时间复杂度 O(n2) 空间复杂度 O(1)
  2. 哈希 时间复杂度 O(n) 空间复杂度 O(n))
  3. 排序再查找 时间复杂度 O(nlogn) 此题返回下标不可行,相似题可行

暴力两次循环

学过其他语言的,很容易写出的代码

impl Solution
{
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {

let len = nums.len();
for i in 0..len {
for j in i+1..len {
if nums[i] + nums[j] == target {
return vec![i as i32, j as i32];
}
}
}

vec![]
}
}

  • 执行用时: 40 ms
  • 内存消耗: 2.1 MB

for循环两次,判断是否相等。
如果要使用数组的迭代器,那第二次循环只能重头开始,需要判断index是否相等。

impl Solution
{
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {

for(i, num_i) in nums.iter().enumerate()
{
for (j, num_j) in nums.iter().enumerate()
{
if i != j && num_i + num_j == target
{
return vec![i as i32, j as i32]
}
}
}
vec![]
}
}

  • 执行用时: 76 ms
  • 内存消耗: 2 MB

HashMap

我们考虑使用HashMap,拿空间换时间。
如果没有在哈希表中就插入,有就返回结果。

use std::collections::HashMap;

impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::with_capacity(nums.len());
for(index,num) in nums.iter().enumerate() {
if let Some(&find) = map.get(&(target-num)) {
return vec![find as i32, index as i32];
}
map.insert(num,index);
}
vec![]
}
}

  • 执行用时: 0 ms
  • 内存消耗: 2.3 MB

需要注意,返回的是索引,所以插入哈希表时key应该是nums中的值,value才是index。

问题与优化思路

问题:
对Rust语法不算熟悉,需要查文档才能知道HashMap的用法。
做算法题,开始得画图来理清自己的思路,确定需求和数据边界,这题中返回下标是首先要确定的需求。

优化思路:
此题如果不返回下标,会有先排序后查找的算法作为X Sum的基础解决算法。
X Sum的解题思路主要是把它转化为(X-1)Sum,最后成为2Sum问题,得到最后的答案。
这其中的转换就是,选出一个元素a,然后就变成target为 -a 的(X-1)Sum 问题。

题型与相似题

题型

  1. 数组
  2. 哈希表

相似题

  1. Two Sum II – Input array is sorted
  2. Two Sum III – Data structure design
  3. 3 Sum
  4. 3 Sum Smaller
  5. 3 Sum Closet
  6. 4 Sum

代码

two_sum

参考资料