ARTS打卡：第二十三周

发表于 | 分类于 | 本文总阅读量 次

ARTS打卡：第二十三周

每周完成一个ARTS：

  1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

Algorithm

15. 3Sum（Medium）

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

链接： https://leetcode.com/problems/3sum/

解题思路

  1. 暴力破解：使用三重遍历来做，最后需注意结果集的去重，时间复杂度为O(n³)，这种解法我就不写出来了
  2. 数组排序 + 双指针
    • 先将数组进行排序
    • 选数组最左的值作为 c，由于要符合 a+b+c=0，所以 c 值必须小于0
    • 使用首尾指针，分别指代a和b，首尾指针双向移动，找出符合公式a+b=-c的 a、b值

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 边界条件
        if(nums == null || nums.length < 3){
            return null;
        }
        // 数组排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0; i < nums.length - 2; i++) {
            // 因为数组是有序的，所以 nums[i] 是最小值，如果 nums[i] > 0，则无解，不符合 a+b+c = 0，c = nums[i]
            if(nums[i] > 0) {
                break;
            }
            // i == 0 || nums[i] != nums[i -1] 目的是防重
            if(i == 0 || nums[i] != nums[i -1]){
                // 选择数组最左的值作为 c，即 -c = sum = a + b，定义首尾指针
            	int sum = 0 - nums[i], first = i + 1, tail = nums.length - 1;
                while(first < tail) {
                    // a + b = -c
                    if(nums[first] + nums[tail] == sum){
                        result.add(Arrays.asLsit(nums[i], nums[first], nums[tail]));
                        // 去重
                        while(first < tail && nums[first] == nums[first+1]){
                            ++first;
                        }
                        while(first < tail && nums[tail] == nums[tail-1]){
                            --tail;
                        }
                        ++first;
                    	--tail;
                    } else if (nums[tail] + nums[tail] < sum){
                        // a + b < -c 则需移动首指针
                        ++first;
                    } else {
                        // a + b > -c 则需移动尾指针
                        --tail;
					}
                }
            }
        } 
        return result;
    }
}

ps：LeetCode的这道题是有问题的，题目中强调：答案中不可以包含重复的三元组，但是加入三元组的判重条件，又会导致通过不了(:зゝ∠)，所谓的不可以包含重复的三元组，就是不能 [0,0,0]，所以下面的答案是没有三元组的判重条件的

结果：

Runtime: 25 ms, faster than 98.84% of Java online submissions for 3Sum.

Memory Usage: 45.5 MB, less than 96.47% of Java online submissions for 3Sum.

复杂度：

时间复杂度：O(n²)

空间复杂度：O(1)

Review

本周阅读：

《 Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads 》，通过阅读这篇技术论文，我们就能知道 Disruptor 它试图解决什么问题，并能了解 Disruptor 这个并发框架为什么那么快的原因。

扩展阅读：

《Dissecting the Disruptor: What’s so special about a ring buffer?》

《Dissecting the Disruptor: How do I read from the ring buffer?》

Tip

这次分享如何在Linux下进行抓包，在Windows下进行抓包，可以点击查看这篇文章：《Wireshark使用详解以及HTTP抓包》。

在Linux下抓包，可以采用 tcpdump

安装命令：yum install tcpdump

简单分享几个命令：

  1. 监控指定网卡上的所有数据

    1
    $ tcpdump -i eth0

  2. 查看指定IP上的进出流量

    1
    $ tcpdump host x.x.x.x

  3. 根据来源和目标进行筛选，

    1
    2
    3
    $ tcpdump src x.x.x.x 
    $ tcpdump dst x.x.x.x
    ps: src = source, dst=destination

  1. 将捕获的数据包保存至文件或读取数据包文件。

    1
    2
    3
    4
    # 使用 -w 保存至文件
    $ tcpdump port 80 -w capture_file
    # 使用 -r 读取文件
    $ tcpdump -r capture_file

想要了解更多内容，小伙伴们可以点击查看：《A tcpdump Tutorial with Examples — 50 Ways to Isolate Traffic》，不想看英文的小伙伴可以点击查看这篇译文：[译]tcpdump 示例教程。

Share

本周继续分享 simviso 团队译制的《斯坦福编译原理》系列视频，这周已更新至25集，感兴趣的小伙伴们，赶紧追起来呀，合集地址：【国外精选视频课】斯坦福编译原理(中文翻译) 合集 更新中。